Seven Languages in Seven Weeks Part 12: Haskell Day 2

It's been awhile, but day 2 of Haskell is complete. I've got a lot less spare time for doing these now that classes have changed up. I'm at work full time and then in class from 6pm to 10pm three days a week plus doing homework, etc. The house also got struck by lightning (everyone is ok and even the damage isn't too bad, all things considered) earlier this week which added more delays.

The first exercise was fairly simple, write a function that takes a list and returns a sorted list. I kind of feel like I cheated on this one, though. I knew the logic that I wanted to use but had to go to google for the syntax. Unfortunately that pretty much gave me the entire answer since it's so short. My base logic was correct though, so that's good.

This function takes the head of a list and then passes it into the filter function looking for all members of the list that are less than the head and then continues to do that recursively for each of those so they are in order and prepends them to the head(s). Then the same is done appending to the head(s) for list members greater than the current head.

module Main where
    list_sort ([]) = []
    list_sort (h:t) = list_sort (filter (< h) t) ++ [h] ++ list_sort (filter (>h) t)

Prelude> :load sort.hs
[1 of 1] Compiling Main             ( sort.hs, interpreted )
*Main> list_sort [1,4,3,2,9,25,10]
[1,2,3,4,9,10,25]

Next up was to do the same thing but allow the user to pass their own function into the sort function as a parameter.

module Main where
    sorter (f, []) = []
    sorter (f, h:t) = sorter(f, filter(f h) t) ++ [h] ++ sorter(f, filter(not . (f h)) t)

    --I'm not quite clear on the not syntax in the second part, it was just taken from the definition of partition.
    --It seems to work, though.
    -- example: sorter((\x y -> if x > y then True else False), [12,3,1])
    -- example: sorter((>),  [12,3,1])

Prelude> :load sort2.hs
[1 of 1] Compiling Main             ( sort2.hs, interpreted )
Ok, modules loaded: Main.
*Main> sorter((\x y -> if x > y then True else False), [12,3,1])
[1,3,12]

The third exercise was to write a function to convert a string in the form of $2,345,678.99 with any number of leading 0s to a number. In most languages that I'm used to working with this probably would have been done with a regular expression, but it's handled a bit differently in Haskell.

module Main where
    tonum :: String -> Double
    --would like to use stripPrefix here, but it doesn't seem to be in
    --my version of ghci although all documentation seems like it should be
    --This is pretty straightforward, though.  Take the string, run it through filter
    --to remove any commas, which is then passed into dropWhile to remove a leading $
    --the result of which is used in dropWhile to remove leading 0s
    --which is finally used by read() which converts a string to a number, a Double in this case
    tonum (str) = read (dropWhile(== '0') (dropWhile(== '$') (filter(/= ',') str))) :: Double

Prelude> :load tonumber.hs
[1 of 1] Compiling Main             ( tonumber.hs, interpreted )
Ok, modules loaded: Main.
*Main> tonum "$0002,345,678.99"
2345678.99

Number four is a bit odd.I suspect the exercise is poorly worded. The exercise is to write a function that takes parameter x and returns a lazy list of every 3rd number and another that takes parameter y and returns a lazy list of every 5th number. Then it says to use composition to combine the two functions to create a lazy list of every 8th number starting with x+y.The problem here is that composition, the. operator, used like f . g, passes the return value of g into function f. Since both of these functions return a list but only take an integer I don't see how you could use composition to combine them. I asked another more experienced Haskell developer and he felt the same as I do. The solution I used with the zipWith function is also how everyone else seems to have completed this exercise.

Note that inc3 and inc5 could also have been done with range and pattern rather than recursion. I went with recursion because that's what the author of the book used in his lazy list examples and I wanted to be sure I understood the concepts he was trying to get across.

module Main where
  inc3 :: Integer -> [Integer]
  inc3 start = start:inc3(start + 3)

  inc5 :: Integer -> [Integer]
  inc5 start = start:inc5(start + 5)

  inc8 :: Integer -> Integer-> [Integer]
  --This is not function composition as the exercise requested
  --I can't figure out how to do it with composition (the . operator)
  --inc5 takes an int and inc3 takes an int, but both return lists of int
  --so I don't see any way these could possibly be combined using composition
  inc8 x y = zipWith (+) (inc3 x) (inc5 y)

Prelude> :load lazylist.hs
[1 of 1] Compiling Main             ( lazylist.hs, interpreted )
Ok, modules loaded: Main.
*Main> take 5 (inc3 1)
[1,4,7,10,13]
*Main> take 5 (inc5 3)
[3,8,13,18,23]
*Main> take 5 (inc8 1 3)
[4,12,20,28,36]

Excercise 5 said to write a partially applied function that takes a parameter and returns half and another that appends \n (an actual newline, not a string literal \n). The partially applied function concept is simple enough, you can create a function that is another function plus just some of the parameters it requires. Then whatever you pass as the parameter to the "new" function gets used as the final parameter of the original function. Haskell also lets you use prefix operators if you want to which makes writing partially applied functions really simple.

*Main> let half = (/ 2)
*Main> half 12
6.0

*Main> let add_newline = (++ "\n")
*Main> add_newline "whee"
"whee\n"
*Main> putStr (add_newline "whee")
whee

There are also a few more exercises that the author suggests if you want something more challenging.

The first of the more challenging exercises is to write a function which takes two integers and returns the greatest common denominator. The built in gcd function was written as a recursive function using some extra Haskell syntax that I am unfamiliar with (or was, after seeing it I learned about it and used it in the next exercise) and is nearly instant even with large numbers while mine has a small delay with larger numbers. The numbers in the example have maybe 1/2 second delay due to generating the lists and then comparing them with intersect and bigger numbers continue to get slower.

module Main where
  import Data.List
  find_gcd :: Int -> Int -> Int
  find_gcd a b = last (intersect
                  [x | x <- [1..a], ((mod a x) == 0)]
                  [y | y <- [1..b], ((mod b y) == 0)])

*Main> :load denom.hs
[1 of 1] Compiling Main             ( denom.hs, interpreted )
Ok, modules loaded: Main.
*Main> find_gcd 109644 20688
12
*Main> gcd 109644 20688
12

Next is generating a lazy list of prime numbers. I never would have come up with the solution for this on my own. I looked up algorithms for finding prime numbers but still didn't have the knowledge of Haskell to implement them. It seems like these might be using a library that I don't have installed, Data.List.Ordered, because I can't import that module and do not have the unionAll function. This wikipedia page has Haskell implementations of the Sieve of Eratosthenes and Euler's Sieve. I was going to try to create a lazy version of Euler's Sieve but the lack of the minus function has stopped that.

The last bit was broken up into a few steps, but I'm posting them all as one program. First was to create a function that takes a string, breaks it up on word boundaries to add a new line, then returns it. After that, add line numbers. Then after adding line numbers, add functions to left, right, and center align the text using spaces for padding.

I had a couple of ways to go about adding the padding. My first thought was to just use printf, but sorting out how much padding to add actually turned into more hassle than I initially expected. I ended up just writing functions to pad to the right or left which took how many spaces to add as a parameter. I chose to add more spaces to the right than left when an uneven number of spaces was needed. For left and right alignment I just combine the output of get_left_padding and get_right_padding which each return just half the padding needed for the whole line. I also just align with the length of the longest word since I don't have set width such as for screen or a piece of paper.

module Main where
  import Data.Char
  import Text.Printf
  import Data.Function (on)
  import Data.List (maximumBy)

  format_text :: String -> String
  format_text str = (unlines . add_nums 1 . words) str

  --These could have been combined into a single format() function
  --which took left, right, or center as a param like the align() function
  format_left :: String -> String
  format_left str = (unlines . add_nums 1 . align x "left" . words) str
                    where x = longest_string (words str)

  format_right :: String -> String
  format_right str = (unlines . add_nums 1 . align x "right" . words) str
                     where x = longest_string (words str)

  format_center :: String -> String
  format_center str = (unlines . add_nums 1 . align x "center" . words) str
                      where x = longest_string (words str)

  add_nums :: Int -> [String] -> [String]
  add_nums counter [] = []
  add_nums counter (h:t) = printf "%d %s" counter h : (add_nums (counter + 1) t)

  -- This was three separate functions but this is more compact
  -- and just as readable and since it's all doing the same thing, aligning, I think it's ok
  align :: Int -> String -> [String] -> [String]
  align len justify [] = []
  align len justify (h:t) = case justify of
    "left" -> (pad_right((get_right_padding len h) + (get_left_padding len h)) h) : align len justify t
    "right" -> (pad_left((get_left_padding len h) + (get_right_padding len h)) h) : align len justify t
    "center" -> ((pad_left (get_left_padding len h) . pad_right (get_right_padding len h)) h) : align len justify t

  --Functions to determine how many spaces to add to the left or right of a string
  get_left_padding :: Int -> String  -> Int
  get_left_padding len str = (len - (length str)) `div` 2

  --if not evenly divisible by 2 then put more padding on the right
  get_right_padding :: Int -> String -> Int
  get_right_padding len str =  ((len - (length str)) `mod` 2) + ((len - (length str)) `div` 2)

  --Functions to determine how many spaces to add to the left or right of a string
  get_left_padding :: Int -> String  -> Int
  get_left_padding len str = (len - (length str)) `div` 2

  --if not evenly divisible by 2 then put more padding on the right
  get_right_padding :: Int -> String -> Int
  get_right_padding len str =  ((len - (length str)) `mod` 2) + ((len - (length str)) `div` 2)

  longest_string :: [String] -> Int
  longest_string str = (length . maximumBy(compare `on` length)) str