Week 3 of CIS 194 was about how to abstract different kinds of recursion patterns with help of map, folds and filter. As a side note, polymorphism was touched upon to show how to define functions that work on several different kinds of data types. Prelude (one of the standard modules of Haskell) was mentioned and encouraged to be explored a bit. Finally total and partial functions were discussed and their differences outlined.
Map, reduce (called fold in Haskell) and filter are very basic tools that show up time after time. Map transforms a list of items to another list of (different kind of) items. Reduce aggregates a list, producing a single value and filter creates a new list that has elements of original list filtered by some logic.
While reduce was familiar to me from Hy, Haskell has several different versions of fold: foldl, foldr and foldl’ (to name few). Their differences are explained nicely in this wiki-article and there are countless questions regarding difference of different folds in stack overflow. Especially if the function used in fold isn’t associative (for example 1 + (2 + 3) equals to (1 + 2) + 3, but 1 – (2 – 3) isn’t same as (1- 2) – 3)) there’s big difference between foldl and foldr.
Map takes function and runs that on each element of a list, producing a new list. Elements in the resulting list don’t have to be of same type as the source list. And filter just produces a new list containing elements that satisfy some test or check.
The single biggest lesson in lecture (besides exploring prelude) was the section about total and partial functions. In this context, partial function is a function that may cause an error when given certain input. Total function on the other hand is guaranteed to work with all possible inputs, without crashing the system. For example, head will cause a crash when called with an empty list, thus it’s a partial function. / (division) on the other hand will work, even when one tries to divide with zero (anything but zero divided by zero yield Infinity and zero divided by zero yield NaN). One should strive to write total functions as much as possible, because then chances of program crashing completely are smaller. It’s easier to build program using well behaving functions as you don’t have to keep track of possible system crash causing inputs.
There were three exercises and below I’m posting one of them, drawing a histogram. The code probably isn’t the cleanest example of Haskell and I’m pretty sure it could be written in more concise format too. But it works and that’s what matters (also doesn’t look completely horrible).
histogram :: [Integer] -> String histogram xs = unlines $ map (drawLine histogramData) $ reverse [(-1)..peak] where histogramData = buildMap xs peak = Map.foldr max 0 histogramData buildMap :: [Integer] -> Map.Map Integer Integer buildMap xs = foldr (Map.alter alterF) Map.empty xs where alterF Nothing = Just 1 alterF (Just n) = Just $ n + 1 drawLine :: Map.Map Integer Integer -> Integer -> String drawLine heights (-1) = take width $ cycle "0123456789" where width = 1 + (fromInteger $ histogramWidth heights) drawLine heights 0 = take width $ repeat '=' where width = 1 + (fromInteger $ histogramWidth heights) drawLine heights n | n > 0 = map glyph [0..(histogramWidth heights)] where glyph i = if (Map.findWithDefault 0 i heights) >= n then '*' else ' ' drawLine _ _ = "" histogramWidth :: Map.Map Integer t -> Integer histogramWidth x | length (Map.keys x) > 0 = maximum $ Map.keys x | otherwise = (-1)
> putStr $ histogram [2, 5, 7, 5, 1] * ** * * ======== 01234567
Overall, this section of CS 194 was more relaxed as there weren’t that many exercises to do or too many new concepts to tackle. Quite looking forward on doing the next section soon.