Haskell Function Application

Question

A bit of a neophyte haskell question, but I came across this example in Haskell's tutorial examples. For "find the last element of a list" there are some obvious versions, like

last' [x] = x
last' (_:xs) = last' xs

But I can't make sense of an alternate version presented:

myLast' = foldr1 (const id)

So, in trying to make sense of what the application of the id function is doing, I tried in ghci:

const id 1 2 -> gives 2

This binds like this:

(const id) 1 2 -> gives 2

And not like this:

 const (id 1) 2 -> gives 1

But I'm not making sense of this. (const id) should translate to something like

`(\x y->x) (\x->x)`

Shouldn't this return a function that simply returns the id of its first element? Or, how is the function order making (const id) behave differently than const?

I'd like to thank the academy, my producer, the director .... — Steve B.
– Steve B., Commented Jan 28, 2010 at 21:08

Chris Conway · Accepted Answer · 2009-07-22 14:50:15Z

31

The definition of const is

const x = \_ -> x

Hence, (const id) is a function which takes one argument and always returns id and

const id 1 2 = (\_ -> id) 1 2
             = id 2
             = 2

The definition of foldr1 is

foldr1 f [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)

If we have

myLast' = foldr1 (const id)

then

myLast' [x] = foldr1 (const id) [x]
              {- definition of foldr1 -}
            = x

and

myLast' (x:xs) = foldr1 (const id) (x:xs)
                 {- definition of foldr1 -}
               = (const id) x (foldr1 (const id) xs)
                 {- definition of const -}  
               = (\_ -> id) x (foldr1 (const id) xs)
                 {- function application -}  
               = id (foldr1 (const id) xs)
                 {- definition of id -}  
               = foldr1 (const id) xs
                 {- definition of myLast' -}  
               = myLast' xs

which agrees with the definition of last'.

edited Jul 22, 2009 at 14:50

answered Dec 5, 2008 at 6:16

Chris Conway

56.2k43 gold badges132 silver badges155 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Steve B. Over a year ago

ahhh. Didn't make the connection of the const returning the function. Thanks for the explanation.

J Cooper Over a year ago

This is a great explanation, and stepping through it I can see how it works. But is foldr1 (const id) really the idiomatic way to do a myLast function? The first example given seems way more clear...

Chris Conway Over a year ago

I wouldn't say it's idiomatic... Haskell geeks enjoy working out how to express things in a "point-free" style, or purely in terms of folds. It becomes a kind of programming puzzle. The first version is much more clear.

Magnus · Accepted Answer · 2008-12-07 20:49:58Z

9

I rely heavily on :t when trying to understand Haskell. In this case:

Prelude> :t const id
const id :: b -> a -> a

might have helped you see what was going on.

answered Dec 7, 2008 at 20:49

Magnus

4,7343 gold badges38 silver badges49 bronze badges

1 Comment

Jay Conrod Over a year ago

To clarify, ":t" is a command you can use in GHCI to print the type of an expression.

Collectives™ on Stack Overflow

Haskell Function Application

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related