Geek Answers Handbook

Find the K'th element in the list using the foldr application and the application ($) function

I am currently in the 6th chapter of Learn Haskell ... Recently, I started working on 99 questions.

The third problem is to find the K'th element from the list. I implemented it with take and zip .

The problem is understanding an alternative solution:

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

I am "almost there", but I do not quite understand. I know the definition of $ , but .. Could you please explain to me the execution order of the above code. Also, is it often used as a solution to various problems, is it idiomatic or just ... acrobatic?

+4
source share
2 answers

If you expand the definition of foldr

 foldr fz (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 based on 0).

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

So he does

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

Moreover, is it often used as a solution to various problems, is it idiomatic or just ... acrobatic

In this case, just acrobatic. foldr must extend the full application before it can return to the forefront by taking tail s, so it is less efficient than a simple workaround.

+7
source

Divide it into two main steps. First, the function replicates tail (n-1) times. So you get something like

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

Now the definition of foldr in the list expands something like this:

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

So this fold will expand to (replace f with $ and all y 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) tail calls made up together. After taking n-1 tails, it simply extracts the first element from the remaining list and gives back.

Another way to write it that will make the composition more explicit (in my opinion) is to be

 elementAt n = head . (foldr (.) id $ replicate (n-1) tail)
+6
source

More articles:


All Articles