I looked at chapter 8 in terror and ran to the (comparative) familiarity

of this chapter.

### Currying

I remember a couple of years ago, when I was looking up Functional

Programming early on, I came across the idea that functional programming

languages didn't take multiple arguments, but returned a function at

each step. I think I scoffed slightly at this idea, which seemed as

ridiculous as the idea that my Dad tried to explain once, that Latin

didn't usually use personal pronouns.

But all of these funny looking function signatures like

> makeChange::Int->[Int]->[Int]

>-- rather than

>-- makeChange :: ( Int [Int] ) -> [Int]

begin to make sense in the concept of currying.

The explanation of the currying simplification, whereby

> reverse xs=foldl revOp[]xs

> where revOp acc x=x : acc

is by steps turned into

> reverse=foldl (flip (:))[]

is instructive (and slightly terrifying. I mean, just look at that

definition!)

### Ex 9.1 simplify a fragment of containsS

> (Polygon pts) `containsS` p

>=let leftOfList=map isLeftOfp

> (zip pts (tail pts ++[head pts]))

> isLeftOfp p'=isLeftOf p p'

> in and leftOfList

Immediate candidate for simplification is:

> isLeftOfp=isLeftOf p

so possibly

>-- untested

> (Polygon pts) `containsS` p

>=and $ map (isLeftOf p)

> (zip pts (tail pts ++[head pts]))

### Ex 92. Show that `flip (flip f)` is the same as `f`

The definition of flip given was:

> flip::(a->b->c)->(b->a->c)

> flip f x y=f y x

`f` is a function (a -> b -> c).

flip (flip f) x y = (flip f) y x

flip f y x = f x y

flip (flip f) x y = f x y

-- so

flip (flip f) = f

### Ex. 9.3. What is the type of ys?

xs = [1,2,3] :: [Float]

ys = map (+) xs

I suppose we have to know what types the functions involved are:

Prelude> :t map

map :: (a -> b) -> [a] -> [b]

Prelude> :t (+)

(+) :: (Num a) => a -> a -> a

(+) works on the same type o Num a. (+) on a single number will return

a function (Float -> Float), so the mapped version should be

> ys::[(Float->Float)]

Let's check it out!

Prelude> let xs = [1,2,3] :: [Float]

Prelude> :t map (+) xs

map (+) xs :: [Float -> Float]

OK, so that's [Float -> Float], it seems that the parentheses aren't

needed here.

### Ex. 9.4. Define a function applyEach

such that

> applyEach[simple 2 2, (+3)]5

>-- => [14,8]

where simple is defined

> simple x y z=x * (y + z)

> applyEach::[a->b]->a->[b]

> applyEach (f:fs) a=f a : applyEach fs a

> applyEach[]_=[]

which is the definition I made for `unmap` in Chapter 5. But we

can do better than that. If we just swap the item and the list, we can

use map:

> applyEach fs a=map apply fs

> where apply f=f a

And of course, if we use the application operator, `($)`, we can

simplify that to

> applyEach fs a=map ($ a) fs

now, as we're swapping the order of parameters, it occurs to me we could

so something with flip:

> applyEach=flip applyEach'

> applyEach' a fs=map ($ a) fs

which can be simplified to:

> applyEach=flip applyEach'

> applyEach' a=map ($ a)

which is

> applyEach=flip (\a->map ($ a))

But I don't know if you can get rid of the remaining parameter somehow.

### Ex. 9.5. Define a function `applyAll`

such that

> applyAll[simple 2 2, (3)]5

>-- => 20

Similarly I think this might be a fold. And it has to work such that

the input and output types are the same so

> applyAll::[a->a]->a->a

Because we're *starting* with the initial value, we don't plug it

into the apply lexical function, but rather use it as the init argument

to foldr.

> applyAll fs a=foldr apply a fs

> where apply f a=f a

Therefore, we can think of simplifying `apply` by currying:

> where apply f=f

and then I really want to do

> where apply=-- Error!

But funnily enough, that's a syntax error :-) As it happens, we can use

the application operator ($) just like above

> applyAll fs a=foldr ($) a fs

Ooo!, and we can do this with a flip, like so

> applyAll=flip . foldr ($)-- dammit, that doesn't work

> applyAll=flip foldr ($)-- neither does that, and it gives a

-- crazy type, that spans multiple

-- lines!

> applyAll=flip $ foldr ($)-- Yay! That's the one.

As you can see, machine gun debugging (inserting and removing operators

at random until things compile) is still a preferred technique…

Ah! But actually, though this gives the same result as before, I'm

a little doubtful

*Main> applyAll [(+2), (*2)] 4

10

I'd expect it to be `4+2=6 *2=12`. The problem will be the use

of foldr!

> applyAll=flip $ foldl ($)

But this gives me an error!:

Occurs check: cannot construct the infinite type: b = a -> b

Probable cause: `$' is applied to too many arguments

In the first argument of `foldl', namely `($)'

In the second argument of `($)', namely `foldl ($)'

I'm not sure what's going on here, apart from that it's an example of

what Hudak mentions about the choice between `foldl` and

`foldr` being about a) efficiency and b) sometimes one of the

options being â€œmore definedâ€ than the other.

### Ex. 9.6. Which of these functions is more efficient?

> appendr, appendl::[a]->[a]->[a]

> appendr=foldr (flip (++))[]

> appendl=foldl (flip (++))[]

I'm not sure what this does, so instead of typing it into ghci I'm going

to try to work it out first.

appendr [1,2] [3,4]

=> foldr (flip (++)) [] [1,2] [3,4]

Er. Actually, no, I'm confused now. I think `foldr op init vs`

is expecting one further argument (vs), but appendr takes 2. So I try

in ghci and indeed it doesn't compile. If I comment the signature line,

then it does with the type signature:

*Main> :t appendr

appendr :: [[a]] -> [a]

So let's try again:

let <<++>> = (flip (++))

appendr [ [1,2], [3,4] ]

=> foldr <<++>> [] [[1,2],[3,4]]

=> [1,2] <<++>> foldr <<++>> [] [[3,4]]

=> [1,2] <<++>> [3,4] <<++>> foldr <<++>> [] []

=> [1,2] <<++>> [3,4] <<++>> []

=> [1,2] <<++>> ( [] ++ [3,4] )

=> [1,2] <<++>> [3,4]

=> [3,4] ++ [1,2]

=> [3,4,1,2]

Perhaps this would be clearer with 3 elements?

appendr [ [1,2], [3,4], [5,6] ]

=> [1,2] <<++>> ([3,4] <<++>> ([5,6] <<++>> []))

=> [1,2] <<++>> ([3,4] <<++>> ([] ++ [5,6]))

=> [1,2] <<++>> ([3,4] <<++>> [5,6])

=> [1,2] <<++>> ([5,6] ++ [3,4])

=> [1,2] <<++>> [5,6,3,4]

=> [5,6,3,4] ++ [1,2]

=> [5,6,3,4,1,2]

appendl [ [1,2], [3,4], [5,6] ]

=> (([] <<++>> [1,2]) <<++>> [3,4]) <<++>> [5,6]

=> ([1,2] ++ []) <<++>> [3,4]) <<++>> [5,6]

=> ([1,2] <<++>> [3,4]) <<++>> [5,6]

=> ([3,4] ++ [1,2]) <<++>> [5,6]

=> [3,4,1,2] <<++>> [5,6]

=> [5,6] ++ [3,4,1,2]

=> [5,6,3,4,1,2]

From the discussion in Chapter 5, we see that concatenating with (++)

takes time proportional to the number of elements in the left-hand list.

`appendl` repeatedly concatenates the left hand side of the list,

so should be slower. (Though in this case, appendr scores 0+2+4=6,

while appendl scores 2+2+2=6, which is equal).

### Ex. 9.7. Define a function `twice`

> (twice (+1)) 2=>4

That's easy enough:

> twice::(a->a)->a->a

> twice op v=op (op v)

Now, what does `twice twice` do? I have no idea, given that

`twice` takes a function (a->a) while `twice` itself

*isn't* such a function. Or… maybe it is if you read it as

(a->a) -> (a->a).

Here, my notes show that I am confused, as I make notes such as â€œGRAAAHâ€

and â€œWTF?â€ as well as going through the (.) and ($) options again:

*Main> :t twice twice

twice twice :: (t -> t) -> t -> t

*Main> :t twice $ twice

twice $ twice :: (t -> t) -> t -> t

*Main> :t twice . twice

twice . twice :: (t -> t) -> t -> t

The end result of this confusion was that `twice op` returns a

function of the same sort as required for `twice`, so `twice
twice` should simply do the operation 4 times. And

`twice twice`

twicewill do it 16 times.

twice

what about â€œtwice(twice twice)â€œ I would think that would be the same as

â€œtwice twice twiceâ€, and in fact it is (though perhaps there are

efficiency concerns again)

### Ex. 9.8. define a function `power`

> power (+2) 5 1=>11

> power::(t->t)->Integer->t->t

> power f n init

>|n==1=f init

>|otherwise=f (power f (n-1) init)

> twice::(a->a)->a->a

> twice f=power f 2

Now, to define something useful… I suppose we can do multiplication,

though to be honest it seems a bit naff:

> mult x y=power (+x) y 0

The second half of this chapter is quite tricky, and I'm tired, so I'm

going to break off here.