# C9 Lectures: Dr. Erik Meijer - Functional Programming Fundamentals Chapter 7 of 13

- Posted: Nov 12, 2009 at 8:42AM
- 68,570 views
- 16 comments

Loading user information from Channel 9

Something went wrong getting user information from Channel 9

Loading user information from MSDN

Something went wrong getting user information from MSDN

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

- Posted: Nov 12, 2009 at 8:42AM
- 68,570 views
- 16 comments

- To download, right click the file type you would like and pick “Save target as…” or “Save link as…”

- It's an easy way to save the videos you like locally.
- You can save the videos in order to watch them offline.
- If all you want is to hear the audio, you can download the MP3!

- If you want to view the video on your PC, Xbox or Media Center, download the High Quality MP4 file (this is the highest quality version we have available).
- If you'd like a lower bitrate version, to reduce the download time or cost, then choose the Medium Quality MP4 file.
- If you have a Windows Phone, iPhone, iPad, or Android device, choose the low or medium MP4 file.
- If you just want to hear the audio of the video, choose the MP3 file.

Right click “Save as…”

In **Chapter 7**, Dr. Meijer teaches us about **Higher-Order Functions**. A function is called higher-order 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 higher-order functions are important and there are some really interesting side-effects of higher-order functions such as defining DSLs as collections of higher-order functions and using algebraic properties of higher-order 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 5

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums, or Contact Us and let us know.

## Follow the discussion

Oops, something didn't work.

## What does this mean?

Subscriptions allow us send you email notifications when new content is added. You need to be signed in to Channel 9 to use this feature.## What does this mean?

Subscriptions allow us send you email notifications when new content is added.sign up for email notifications?

We have reached the halfway point!

The equational reasoning part on the append operator (++) is wrong. This is what Erik wrote:

This contains several errors:

A correct way to define append would be:

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!

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:

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:

Right

To be clear to everyone: What I'm saying is that the

equalitiesare 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(r|l) consume the whole list before producing a result.

Here is my take on both using foldl

I'd say its easier to implement takeWhile using foldr:

Also, foldr most definitely does not consume the whole list before producing a result. Take this definition:

As you can see in the cons case; foldr calls

`f`

with`x`

and the result of a recursive call.However, since Haskell is lazy,

`f`

gets executedbeforethe result of the recursive call is computed. If`f`

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`

first recurses, before executing the`f`

function that produces the result value.So calling the

`takeWhile'`

, defined below, with an infinite list will result in an infinite computation.Nice post Tom.

So much to learn.

I much prefer this for reverse:

The 'foldl' expresses the eagerness required by reverse, and the 'flip (' expresses the all-pairs 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.

3) Redefine map f and filter p using foldr.

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).

I get

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) [] xs

Sohail Qayum Malik

## Remove this comment

## Remove this thread

Close