Higher Order Functions - Maps, Filters and Folds

Higher order functions is a fancy term for functions that take other functions as parameter. Having said that there is an interesting way to look at this as a paradigm shift in the way we think about functions. The normal way we use functions is to say to the function here is some "data" (parameters) can you please run your logic on my data, in your context. On the other hand with higher order functions you are saying here is some "code", can you please run this "code" for me in your context (which may include data/state). In other words we are passing code to a function instead of data (parameters).

import Graphics.Element exposing (..)
import List exposing (..)

firstTenPowersOfTwo = map ((^)2) [1..10]

sumList : number -> List number -> number
sumList initialValue =
  List.foldr (+) initialValue

main =
  flow down [print "The first ten powers of 2 are : "    firstTenPowersOfTwo
   ,print "The sum of the elements of the list [1..10] : " (sumList 0 [1..10])
  ]

print message value = show (message ++ (toString value))

Exercises

• Implement the cartesian product of two lists. Given two lists l1= [1,2,3] l2=[1,2,3,4] output the list l3= [(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4)] (This exercise really illustrates how difficult it is to code until you have mastered the functional programming idioms.)

import Html exposing (text,ul,li)
import List exposing (..)

l1 =[1..3]
l2=[1..4]

l3 = concatMap (\f -> map f l2) (map (,) l1) 

main = ul[][print "The cartesian product of : " l1
            , print "and " l2
            , print " is " l3
           ]
print message value = li [][text (message ++ (toString value))]

How do we think about this using types and functional programming. First look at the inputs and outputs. You are given two lists as inputs and need to output a list of tuples.

How do we think about this using types and functional programming. First look at the inputs and outputs. You are given two lists as inputs and need to output a list of tuples. Tuples are created by the tuple constructor ((,)).

Now, think of applying the tuple constructor to a list (l1) using a map and partial application of functions (in this case the function is the tuple constructor, and the first argument is each element of the list).

As you can see this gives us a list of functions that take one argument and return a tuple. Now we have to "apply" the list of functions we just created to the list l2. If we are given just one function we know how to do that you can use a map. But now we have to do this for each element of the list of functions!

We can do this using a map and a lambda ((\f -> map f l2)) function. We are almost done. We now have a list of lists which we need to flatten. There is function in the library to do just that! This function is called concatMap which combines map and flatten. So there you have it a nice clean compact solution! Surprisingly with this kind of code the errors you make when writing this code are often type errors, since there is little else to manipulate!

You should look up the definition of concatMap and other functions defined in the List module list docs.