CS431 Segment 4: Haskell

References

Learn You a Haskell for Great Good
Real World Haskell
Community web site
Haskell is an advanced purely functional programming language. An open source product of more than twenty years of cutting edge research, it allows rapid development of robust, concise, correct software. With strong support for integration with other languages, built-in concurrency and parallelism, debuggers, profilers, rich libraries and an active community, Haskell makes it easier to produce flexible, maintainable high-quality software.

--- Haskell.Org
Haskell Cheatsheet

Lecture Notes Etc

Assignments

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)
(a) Bliss
Non-Monadic Warmup: Define sum2n :: Integer -> Int which calculate the sum of the digits of 2ⁿ, 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.