Skip to content

Instantly share code, notes, and snippets.

@ksassnowski
Last active November 3, 2016 11:39
Show Gist options
  • Save ksassnowski/cf499e40a6a1fdff2ea9644487a772b8 to your computer and use it in GitHub Desktop.
Save ksassnowski/cf499e40a6a1fdff2ea9644487a772b8 to your computer and use it in GitHub Desktop.
Trying to understand `filterM (const [True, False]) [1..5]`
-- Given a list of numbers, generate a list of all possible sums.
-- Solution
map sum $ filterM (const [True, False]) [1..5]
-- Manual evaluation of `filterM (const [True, False]) [1..5]` using repeated substitution
filterM (const [True, False]) [1..5]
-- replace `filterM` with its definition
\p -> foldr (\x -> liftA2 (\flg -> if flg then (x:) else id) (p x)) (pure []) (const [True, False]) [1..5]
-- apply `(const [True, False])` to the lambda expression
foldr (\x -> liftA2 (\flg -> if flg then (x:) else id) ((const [True, False]) x)) (pure []) [1..5]
-- perform the first iteration using 1
liftA2 (\flg -> if flg then (1:) else id) ((const [True, False]) 1) (pure [])
liftA2 (\flg -> if flg then (1:) else id) [True, False] (pure [])
-- liftA2 is defined as
-- fmap f a <*> b
fmap (\flg -> if flg then (1:) else id) [True, False] <*> (pure [])
-- This is building a cartesian product, in this case with the empty list
-- In this instance, the cartesian product would be every possible list, where I use the element from the first list
-- (in this case the 1), and where I don't use it.
[(1:), id] <*> (pure [])
-- (<*>) is implemented for lists as follows
[f x | f <- [(1:), id], x <- (pure [])]
[[1], []]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment