This is the code that I came upon somewhere but want to know how this works:
findIndices :: (a -> Bool) -> [a] -> [Int]
findIndices _ [] = []
findIndices pred xs = map fst (filter (pred . snd) (zip [0..] xs))
Output: findIndices (== 0) [1,2,0,3,0] == [2,4], where pred is (==0) & xs is [1,2,0,3,0]
I'll show some of my understanding:
(zip [0..] xs)
What the above line does is put indices to everything in the list. For the input given above, it would look like this: [(0,1),(1,2),(2,0),(3,3),(4,0)].
(pred . snd)
I found that this means something like pred (snd (x)). My question is, is x the list made from the zip line? I'm leaning towards yes but my guess is flimsy.
Next, is my understanding of fst and snd. I know that
fst(1,2) = 1
and
snd(1,2) = 2
How do these two commands make sense in the code?
My understanding of filter is that it returns a list of items that match a condition. For instance,
listBiggerThen5 = filter (>5) [1,2,3,4,5,6,7,8,9,10]
would give [6,7,8,9,10]
My understanding of map is that it applies a function to every item on the list. For instance,
times4 :: Int -> Int
times4 x = x * 4
listTimes4 = map times4 [1,2,3,4,5]
would give [4,8,12,16,20]
How does this work overall? I think I have been comprehensive in what I know so far but can't quite put the pieces together. Can anybody help me out?
In Haskell we like to say, follow the types. Indeed the pieces connect as if by wires going from type to corresponding type:
( first, function composition is:
(f >>> g) x = (g . f) x = g (f x)
(f >>> g) = (g . f) = \x -> g (f x)
and function composition type inference rule is:
f :: a -> b -- x :: a
g :: b -> c -- f x :: b
------------------------- -- g (f x) :: c
f >>> g :: a -> c
g . f :: a -> c
Now, )
findIndices :: (b -> Bool) -> [b] -> [Int]
findIndices pred = \xs -> map fst ( filter (pred . snd) ( zip [0..] xs ))
= map fst . filter (pred . snd) . zip [0..]
= zip [0..] >>> filter (snd >>> pred) >>> map fst
---------------------------------------------------------------------------
zip :: [a] -> [b] -> [(a, b)]
zip [0..] :: [b] -> [(Int,b)]
---------------------------------------------------------------------------
snd :: (a,b) -> b
pred :: b -> Bool
------------------------------------
(snd >>> pred) :: (a,b) -> Bool
---------------------------------------------------------------------------
filter :: (t -> Bool) -> [t] -> [t]
filter (snd >>> pred) :: [(a,b)] -> [(a,b)]
filter (snd >>> pred) :: [(Int,b)] -> [(Int,b)]
---------------------------------------------------------------------------
fst :: (a, b) -> a
map :: (t -> s) -> [t] -> [s]
map fst :: [(a,b)] -> [a]
map fst :: [(Int,b)] -> [Int]so, overall,
zip [0..] :: [b] -> [(Int,b)]
filter (snd >>> pred) :: [(Int,b)] -> [(Int,b)]
map fst :: [(Int,b)] -> [Int]
---------------------------------------------------------------------------
findIndices pred :: [b] -> [Int]You've asked, how do these pieces fit together?
This is how.
With list comprehensions, your function is written as
findIndices pred xs = [ i | (i,x) <- zip [0..] xs, pred x ]
which in pseudocode reads:
"result list contains i for each (i,x) in zip [0..] xs such that pred x holds".
It does this by turning the n-long
xs = [a,b,...,z] = [a] ++ [b] ++ ... ++ [z]
into
[0 | pred a] ++ [1 | pred b] ++ ... ++ [n-1 | pred z]
where [a | True] is [a] and [a | False] is [].