Currently I’m studying the book Learn You a Haskell For Great Good!. In chapter 7, section Data.Map, I try to implement a function that takes a key and a list, filters the list so that only matching keys remain, gets the first key-value that matches and returns the value.
Here’s the function I defined :
findKeyFoldr :: (Eq k) => k -> [(k, v)] -> Maybe v
findKeyFoldr key = foldr (\x acc -> if fst x == key then Just (snd x) else acc) Nothing
I was confused by the following things :
The lambda is an expression also a function, if (fst x == k) is true it should returns snd x. But why these snd x didn’t output? This confuses me because at first I thought “The first element you fold and satifies the if condition should be the one we want” so I use foldl.
I thought somehow scanr is the function I want, i.e. it allows me to foldr and also allows the lambda returns during the process. But when I try to change foldr to scanr, as follows :
findKeyScanr :: (Eq k) => k -> [(k, v)] -> Maybe v
findKeyScanr key = scanr (\x acc -> if fst x == key then Just (snd x) else acc) Nothing
scanr is like foldr except that it returns every intermediate result (from the right). So for example
scanr (+) 0 [1,2,3] = [6, 5, 3, 0]
GHC is warning you because what you’re saying is essentially that you want all the results of your fold version as you keep dropping elements from your list from the left, which isn’t what you said your function does (you only want it to return one result)
I’m honestly not sure I understand your initial problem. The foldr version seems to work fine for me?
As for the lambda, the best way to understand foldr is as a constructor substitution. if you have a list like [1,2,3], it’s really made of (:) and [] constructors ([1,2,3] = 1 : (2 : (3 : [])). foldr f z now replaces every (:) with f and the final [] with 0. so
foldr (+) 0 [1,2,3] = 1 + (2 + (3 + 0)) = 6
So in your case, the first argument is the element of the list you’re currently looking at and the second argument is the result of recursively processing the remaining list. If you found the element you’re looking for, returning that from the lambda and ignoring the second argument makes the entire fold return it and in effect makes the iteration stop (because you’re never evaluating the lazy second argument).
So the foldr should do exactly what you want it to do!
Thank you very much! I think I misunderstand how foldr works. So in my case, when the lambda returns, then the whole findKeyFoldr will return and stop right?
The formula to memorize for foldr is: foo = foldr step base means:
-- base is used for base case
foo [] = base
-- step is used for induction step
foo (x:xs) = step x (foo xs)
-- i.e., "acc" receives the recursive call.
-- This is why I never call it "acc", I call it r.
Applied to findKeyFoldr:
findKeyFoldr key [] = Nothing
findKeyFoldr key (x:xs) = if fst x == key then Just (snd x)
else findKeyFoldr key xs