5

I'm currently at 6th chapter of Learn you a Haskell... Just recently started working my way on 99 questions.

The 3rd problem is to find the K'th element of a list. I've implemented it using take and zip.

The problem I have is understanding the alternate solution offered:

elementAt''' xs n = head $ foldr ($) xs 
                     $ replicate (n - 1) tail

I'm "almost there" but I don't quite get it. I know the definition of the $ but.. Can you please explain to me the order of the execution of the above code. Also, is this often used as a solution to various problems, is this idiomatic or just... acrobatic ?

2 Answers 2

7

If you expand the definition of foldr

foldr f z (x1:x2:x3:...:[]) = x1 `f` x2 `f` x3 `f`... `f` z

you see that elementAt''' becomes

elementAt''' xs n = head (tail $ tail $ ... $ tail $ xs)

(note: it should be replicate n tail instead of replicate (n-1) tail if indexing is 0-based).

So you apply tail to xs the appropriate number of times, which has the same result as drop (n-1) xs if xs is long enough, but raises an error if it's too short, and take the head of the resulting list (if xs is too short, that latter would also raise an error with drop (n-1)).

What it does is thus

  • discard the first element of the list
  • discard the first element of the resulting list (n-1 times altogether)
  • take the head of the resulting list

Also, is this often used as a solution to various problems, is this idiomatic or just... acrobatic

In this case, just acrobatic. The foldr has to expand the full application before it can work back to the front taking the tails, thus it's less efficient than the straightforward traversal.

1
  • I haven't considered last expression as a list of partially applied functions, it's much clearer now. Jan 25, 2013 at 17:20
6

Break it down into the two major steps. First, the function replicates tail (n-1) times. So you end up with something like

elementAt''' xs n = head $ foldr ($) xs [tail, tail, tail, ..., tail]

Now, the definition of foldr on a list expands to something like this

foldr f x [y1, y2, y3, ..., yn] = (y1 `f` (y1 `f` (... (yn `f` x))) ...)

So, that fold will expand to (replace f with $ and all the ys with tail)

foldr ($) xs [tail, tail, tail, ..., tail] 
= (tail $ (tail $ (tail $ ...  (tail xs))) ... )
{- Since $ is right associative anyway -}
= tail $ tail $ tail $ tail $ ... $ tail xs

where there are (n-1) calls to tail composed together. After taking n-1 tails, it just extracts the first element of the remaining list and gives that back.

Another way to write it that makes the composition more explicit (in my opinion) would be like this

elementAt n = head . (foldr (.) id $ replicate (n-1) tail)
2
  • when doing function composition we must use only functions so, id in this case acts as a place holder, it is composed further as a whole with head so the argument (list) that gets passed to the function actually gets passed to the id function, is that correct ? Is id used as a place-holder in these cases with foldr ? Jan 25, 2013 at 19:00
  • 2
    @durmitor: a slightly more mathematical way of looking at it is this: the type a -> a forms a monoid with function composition as the binary operation and id :: a -> a as the identity, because if f, g, h :: a -> a, then f . (g . h) == (f . g) . h and f . id == id . f == f. So just like foldr (+) 0 sums a list of numbers, returning 0 for the empty list, foldr (.) id composes a list of functions that share the same argument and result type, returning id (the function that "does nothing") for the empty list. Jan 25, 2013 at 19:23

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.