I have functions defined as follows:

distance3 :: String -> String -> Float
distance3 x y = fromIntegral $ abs $ length x - length y

distanceFilter :: (String -> String -> Float) -> Float -> String
  -> [String] -> [String]
distanceFilter f d s ss = filter (\x -> f s x <= d) ss

The distanceFilter returns all the strings in ss that are at most d distance away from s.

It works as it is supposed to, but I have trouble understanding the inner workings of

filter (\x -> f s x <=d) ss

Obviously the \x -> takes a string from the list ss and applies it to the function f as the second parameter, but how does it do that? How does it know how to take the element? How does that lambda expression work?

CodePudding user response：

\x -> f s x <= d constructs a function that takes a string and returns a Bool, it thus has type String -> Bool. It is equivalent to defining a function go like:

go :: String -> Bool
go x = f s x <= d

and thus calling this function go as filter predicate.

filter will call the predicate on all items. It is implemented as ^[src]:

filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

For an empty list it thus returns an empty list, and for a non-empty list, it calls pred with x as parameter, and if the predicate returns True, it yields x. In both cases it recurses on the rest of the list.

So the filter calls the predicate with the elements of the list, and since the lambda expression thus is a function that takes such parameter as input, it can be used to determine whether it should yield an element x or not.

CodePudding user response：

distanceFilter f d s ss = filter (\x -> f s x <= d) ss

There are two separate aspects to your question:

1. The lambda "closes" over the values from the outer scope. In this case, f, s and d in (\x -> f s x <= d) refer to the parameters of the function and get their values from the arguments that are passed in. This is called a "closure". You can do some more research on your own to understand more deeply.

2. filter determines what values are passed as x to the lambda. By definition, filter f xs applies the function f to each element of the list xs. So x in your lambda will be each element of ss in turn. Implementing your own version of filter is a great exercise to understand how it works.