CS431 Segment 4: Haskell

References

Lecture Notes Etc

Assignments

  1. Happy Feet!

    The function ++ concatenates (i.e., appends) two lists.

        Prelude> :t (++)
        (++) :: [a] -> [a] -> [a]
    
        Prelude> ['f','u'] ++ "bar"
        "fubar"
    
    Define +++ which takes two lists, each possibly infinite, and returns a list which contains elements of the lists it is given, in the same order they appeared, but interleaved in such a way that any element that appears in either argument ultimately appears in the result.

    Define cantor :: [[a]] -> [a] which similarly takes a (possibly infinite) list of (possibly infinite) lists and interleaves them in such a way that all elements in any of the lists in the input list appear at some point in the result list.

    (+++) :: [a] -> [a] -> [a]
    
    cantor :: [[a]] -> [a]
    
    (my solution)

    Define depthFirst and breadthFirst with

    data Tree a = Empty | Node a (Tree a) (Tree a) deriving Show
    depthFirst :: Tree a -> [a]
    breadthFirst :: Tree a -> [a]
    
    which traverse a tree giving the elements of the tree as a list, in either depth-first or breadth-first order. Example:
    *Main> :load tre.hs
    [1 of 1] Compiling Main             ( tre.hs, interpreted )
    Ok, modules loaded: Main.
    
    *Main> depthFirst (Node 1 (Node 2 Empty (Node 3 Empty Empty)) (Node 4 Empty Empty))
    [1,2,3,4]
    
    *Main> breadthFirst (Node 1 (Node 2 Empty (Node 3 Empty Empty)) (Node 4 Empty Empty))
    [1,2,4,3]
    
    (my solution 1 or 2)
  2. (a) Bliss

    Non-Monadic Warmup: Define sum2n :: Integer -> Int which calculate the sum of the digits of 2n, where n is its argument. Eg,

    Prelude> :l h2.hs
    *Main> sum2n 1000000
    1351546
    
    Make your definition as elegant and concise as possible. Extra kudos if you don't read my hints, enforced via honor system.

    (b) Monadic Bliss!

    Use a list monad to re-solve the SEND+MORE=MONEY cryptogram problem.

    For efficiency, you can make a file foo.hs ending with

    main = show (calcSolution)
    
    and compile it with
    ghc -O9 -o foo foo.hs
    
    and then run the executable foo which will print the result. This can result in dramatic speedups.