Functional Processing of a List
Haskell, Iteration 5
The previous exercise in Haskell of writing recursive definitions of factorial is grossly misleading for two reasons. First, very, very few programs require the computation of factorials. Second, you used recursion which Haskellers don't typically use (directly).
A list is a common data structure, and Haskell implements one,
known as a List. Haskell's standard prelude (the
default libraries) defines several useful methods which iterate (or
recurse) over the list for you. You'll look at a couple of these
helpful functions.
Set Up
- Create a new folder
_languages/haskell/iteration05. - Create a new tester
MapFilterFoldTestin this folder. - Create a new
Rakefilein this folder.
Take a look at the Haskell templates.
Mapping a Function over a List
The map function takes as arguments another
function and a list. The function is applied to each element of the
list, and a new list with the results is returned.
GHCi is GHC's interactive environment (i.e., command-line interpreter). GHC is the Glasgow Haskell Compiler.
Try the Haskell interpreter to try this out.
In a terminal, run ghci. Run any command with a
Prelude> prompt in the rest of this iteration.
Prelude> negate 5 Prelude> negate 45 Prelude> negate (negate 5)
Add a test_negate test variable in
MapFilterFoldTest, and write assertions for these
examples. Compile, and green bar.
Now what if you had a whole list of numbers you wanted to negate?
Prelude> map negate [1, 2, 3] Prelude> map negate [-1, 2, -3] Prelude> map negate []
Add a test_map_negate test variable in
MapFilterFoldTest, and write assertions for these
examples. Compile, and green bar.
Haskell is happy to create new functions out of partially
evaluating a function. That is, * is a function that
multiplies two numbers together. 2* partially
evaluates *, resulting in another function that takes
one argument and multiplies 2 by it. This is known as
currying a function.
Order matters. So try this with division:
I use a let to demonstrate that the currying does
result in a separate function. You could write (2/) 4
and (/2) 4 instead and see what that does.
Prelude> let f = (2/) in f 4 Prelude> let f = (2/) in f 8 Prelude> let f = (/2) in f 4 Prelude> let f = (/2) in f 8
Add a test_currying_divison test variable in
MapFilterFoldTest, and write assertions for these
examples. Compile, and green bar.
You can map a curried function.
A let seems less necessary to me here since it's
clearer that map needs a function for its first
argument.
Prelude> map (2/) [1, 2, 3, 4]
Add a test_mapping_curried_divison test variable in
MapFilterFoldTest, and write assertions for these
examples and others you come up with. Compile, and green
bar.
Something to consider for the future: what if you had a very
long list and a lengthy computation? What if you had multiple cores
or multiple processors? What if someone wired map to
do things in parallel for you? Parallelism for free!
Filtering Values
Prelude> filter even [1, 2, 3, 4] Prelude> filter even [2, 4] Prelude> filter even [1, 3] Prelude> filter even [1..20] Prelude> filter even []
Try the examples in GHCi. Then write an appropriate test
variable in MapFilterFoldTest, compile, and green
bar.
mod computes the modulus of two numbers. (The C
family of languages use % for this same computation.)
You can use mod as a normal named function (e.g.,
mod n 2) or as an operator (e.g., n `mod`
2).
You can also write inline functions like this: \n -> n
+ 1 or \n -> mod n 2 == 0. This is known as
a lambda abstraction. So one could define
even like this:
even = \n -> mod n 2 == 0
Or, instead of even in the examples above, you
could use this:
filter (\n -> mod n 3 == 0) [1..20]
Of course, even is already defined, so what's the
point? Well, what if you want to find the multiples of 3?!
Write another test variable for filtering out multiples of 3. Compile, and green bar.
Folding
Consider this C loop:
int sum = 0; for (int i = 0; i < length; i++) sum = sum + array[i];
It adds up all the values in the array named
array.
Haskell has a simpler way:
Prelude> foldl (+) 0 [1, 2, 3, 4]
In this example, the 0 is equivalent to the
sum = 0 in the original C. [1, 2, 3, 4]
is an explicit list for array.
Try a few other examples with different lists and with
*. Then write, compile, and green bar another test
variable.
Haskell also has a foldr function. Hint:
foldl computes from the left; foldr
computes from the right.
Prelude> foldl (+) 0 [1, 2, 3, 4] Prelude> foldr (+) 0 [1, 2, 3, 4] Prelude> foldl (-) 0 [1, 2, 3, 4] Prelude> foldr (-) 0 [1, 2, 3, 4]
Try some more examples, with different lists and with
/ (and not +). Then write, compile, and
green bar another test variable.