C9 Lectures: Dr. Erik Meijer  Functional Programming Fundamentals Chapter 7 of 13
Description
In Chapter 7, Dr. Meijer teaches us about HigherOrder Functions. A function is called higherorder if it takes a function as an argument and returns a function as a result:
twice :: (a > a) > a > a
twice f x = f (f x)
The function twice above is higher order because it takes a function (f x) as it first argument and returns a function (f(fx))
Dr. Meijer will elaborate on why higherorder functions are important and there are some really interesting sideeffects of higherorder functions such as defining DSLs as collections of higherorder functions and using algebraic properties of higherorder functions to reason about programs.
You should watch these in sequence (or skip around depending on your curent level of knowledge in this domain):
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Chapter 12
Chapter 13
Download
Download this episode
 High Quality WMV (1020.4 MB)
 MP3 (21.0 MB)
 Low Quality MP4 (284.7 MB)
 Mid Quality WMV (369.4 MB)
More episodes in this series
C9 Lectures: Dr. Erik Meijer  Functional Programming Fundamentals Chapter 8 of 13
Related episodes
C9 Lectures: Dr. Erik Meijer  Functional Programming Fundamentals Chapter 13 of 13
C9 Lectures: Dr. Erik Meijer  Functional Programming Fundamentals Chapter 12 of 13
C9 Lectures: Dr. Erik Meijer  Functional Programming Fundamentals Chapter 10 of 13
C9 Lectures: Dr. Erik Meijer  Functional Programming Fundamentals Chapter 9 of 13
C9 Lectures: Dr. Erik Meijer  Functional Programming Fundamentals Chapter 8 of 13
C9 Lectures: Dr. Erik Meijer  Functional Programming Fundamentals Chapter 5 of 13
C9 Lectures: Dr. Erik Meijer  Functional Programming Fundamentals, Chapter 3 of 13
C9 Lectures: Dr. Erik Meijer  Functional Programming Fundamentals, Chapter 1 of 13
C9 Lectures: Graham Hutton  How To Be More Productive
C9 Lectures: Dr. Ralf Lämmel  Going Bananas
The Discussion

We have reached the halfway point!

The equational reasoning part on the append operator (++) is wrong. This is what Erik wrote:
xs ++ ys = foldr (:) ys xs ≡ { 1 } (++) ys xs = foldr (:) ys xs ≡ { 2 } (++) ys = foldr (:) ys ≡ { 3 } (++ ys) = foldr (:) ys ≡ { 4 } (++) = foldr (:)
This contains several errors: The first equality is wrong because the arguments are flipped: xs ++ ys ≡ (++) xs ys
 The second equality is true, although since the arguments of append are flipped, the function doesn't have the correct behaviour
 The third equality is wrong because it's flipping the arguments again. Although actually, (++ ys) isn't a valid way to define a function, so you can't write this down in Haskell. But if this were valid Haskell, the the behaviour of this append operator would be correct again.
 The fourth equality is wrong again because it once again flips the arguments.
A correct way to define append would be:(++) = flip (foldr (:))
Having said all that, I really like this series.
Keep on going Erik!

A function that returns a function? That is clear: It's a curried function!
a > b // function a > b > c // curried function (a > b) > c // but a > (b > c) // vs
Apparently, if history be the judge, currying ought to be called Schönfinkeling and curried functions Schönfinkeled functions after the true inventor of this transformation, Moses Schönfinkel. Sad fate: his papers were burned for heating by his neighbors and he ended up in a sanatorium! Maybe currying is safer after all.

I don't think it's wrong at all. He hasn't flipped the arguments, he puts "ys" as the base case for the fold, meaning it will end up "to the right" (hence the "r" in foldr).
EDIT: Ah, I see what you mean, I thought you meant the first "=" sign. sorry about that, anyway. I'll keep this here because it's neat.
Put this in a Haskell file:
import Test.QuickCheck prop_Concat :: [Int] > [Int] > Bool prop_Concat xs ys = xs ++ ys == foldr (:) ys xs
This code defines a quickCheck property, which is a way of automatically generating tests in Haskell. You specify what you expect to be true for the inputs, and it generates tons of data for you and verifies that the property is indeed true.
Then open it in GHCi (or hugs, I think) and do:
*Main> quickCheck prop_Concat OK, passed 100 tests

Right
To be clear to everyone: What I'm saying is that the equalities are wrong. The first definition is perfectly fine.
Also sylvan: Very nince demo of QuickCheck, and a good thing you put a type signature on
prop_Concat
.When I started using QuickCheck I didn't do that and GHCi defaulted that kind of a function to:
prop_Concat :: [()] > [()] > Bool
So the tests all ran OK and I ended up submitting a wrong solution to an exercise to my teacher...

Again nice lecture!
A comment about implementing takeWhile and dropWhile using foldr. These are functions to take or drop elements at the beginning of a list. So, I think it would be easier to implement them using foldl (fold left). Can it be done with foldr? I’m not sure. The drawback to implement them with fold is that they would be useless when dealing with infinite lists. That is because fold(rl) consume the whole list before producing a result.
Here is my take on both using foldl
takeWhile' :: (a > Bool) > [a] > [a] takeWhile' p = snd . foldl (\(e,v) x > if e then (e,v) else if p x then (False,v++[x]) else (True,v)) (False,[]) dropWhile' :: (a > Bool) > [a] > [a] dropWhile' p = snd . foldl (\(e,v) x > if e then (e,v++[x]) else if p x then (True,v) else (False,v++[])) (False,[])

I'd say its easier to implement takeWhile using foldr:
takeWhile p = foldr (\x xs > if p x then x : xs else []) []
Also, foldr most definitely does not consume the whole list before producing a result. Take this definition:foldr :: (a > b > b) > b > [a] > b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs)
As you can see in the cons case; foldr callsf
withx
and the result of a recursive call.
However, since Haskell is lazy,f
gets executed before the result of the recursive call is computed. Iff
decides to never inspects its second argument, the recursive call will never be evaluated. So that's why you can do:takeWhile (<4) [0..]
However, you are right about foldl.
foldl :: (a > b > a) > a > [b] > a foldl f z [] = z foldl f z (x:xs) = foldl (f z x) xs
foldl
first recurses, before executing thef
function that produces the result value.So calling the
takeWhile'
, defined below, with an infinite list will result in an infinite computation.takeWhile' p = foldl (\ys x > if p x then ys ++ [x] else ys) []

Nice post Tom.
So much to learn.

I much prefer this for reverse:
reverse = foldl (flip (:)) []
The 'foldl' expresses the eagerness required by reverse, and the 'flip (' expresses the allpairs transposition.

These are great lectures. Unfortunately, Silverlight running on Safari 4.0 / Snow Leopard is terrible.
Microsoft would be well served to upgrade to Apple's QuickTime, but I'm confident that would never happen.

Just click on the Media Downloads link and choose MP4.....
C

What I don't get is the definition of reverse:
Shouldn't it be
reverse' = foldr (\x xs > xs++[x]) []

homework:
2) Express the comprehension [f x  x < xs, p x] using the functions map and filter.
mapfilter :: (a > b) > (a > Bool) > [a] > [b] mapfilter f p = map f . filter p
3) Redefine map f and filter p using foldr.
map' :: (a > b) > [a] > [b] map' f = foldr (\x v > f x:v) [] filter' :: (a > Bool) > [a] > [a] filter' p = foldr (\x v > if p x then x:v else v) []

I *think* Erik said that using the sum . map variant on length would be less efficient but it runs faster for me. (using timing method from here).
import Text.Printf import Control.Exception import System.CPUTime time :: IO t > IO t time a = do start < getCPUTime v < a end < getCPUTime let diff = (fromIntegral (end  start)) / (10^12) printf "Computation time: %0.3f sec\n" (diff :: Double) return v len1 = sum . map ( \ _ > 1 ) len2 = foldr ( \ _ n > n+1) 0 limit = 500000 main = do putStrLn "Len1:" time $ len1 [1..limit] `seq` return () putStrLn "Len2:" time $ len2 [1..limit] `seq` return ()
I get
*Main> :run main Len1: Computation time: 0.719 sec Len2: Computation time: 1.141 sec

Hey,
map :: (a > b) > [a] > [b]
map f [] = []
map f (x:xs) = f x : Main.map f xs
map' :: (a > b) > [a] > [b]
map' f [] = []
map' f xs = Main.foldr (\x xs > f x : xs) [] xs
filter :: (a > Bool) > [a] > [a]
filter f [] = []
filter f (x:xs)  f x = x : Main.filter f xs
 otherwise = Main.filter f xs
filter' :: (a > Bool) > [a] > [a]
filter' f [] = []
filter' f xs = Main.foldr (\x xs > if f x then x : xs else xs) [] xs
 Need Integral class, since method div is provided there
even :: Integral a => a > Bool
even a = if ((a `div` 2)*2) == a then True else False
foldr :: (a > b > b) > b > [a] > b
foldr f v [] = v
foldr f v (x:xs) = f x (Main.foldr f v xs)Sohail Qayum Malik

length' = sum . map(\_ > 1)
length'' = (foldr (\x xs > x + xs) 0) . (foldr (\_ xs > [1] ++ xs) [])all' :: (a > Bool) > [a] > Bool
all' p as = foldr (\x xs > x && xs) True $ foldr (\x xs > if p x then True : xs else False : xs) [True] as
all' p xs = foldr (\x xs > p x && xs) True xs
any' :: (a > Bool) > [a] > Bool
any' p xs = foldr (\x xs > p x  xs) False xs
takewhile' :: (a > Bool) > [a] > [a]
takewhile' p xs = foldr (\x xs > if p x then x : xs else xs) [] xs
dropwhile' :: (a > Bool) > [a] > [a]
dropwhile' p xs = foldr (\x xs > if not (p x) then x : xs else xs) [] xsSohail Qayum Malik