Removing syntactic sugar: List comprehension in Haskell

by

List comprehensions (in fact, Monad comprehensions) can be desugared into do notation.

do i <- [1..4]
   j <- [i+1..4]
   return (i,j)

Which can be desugared as usual:

[1..4]   >>= \i ->
[i+1..4] >>= \j ->
return (i,j)

It is well known that a >>= \x -> return b is the same as fmap (\x -> b) a. So an intermediate desugaring step:

[1..4] >>= \i -> 
fmap (\j -> (i,j)) [i+1..4]

For lists, (>>=) = flip concatMap, and fmap = map

(flip concatMap) [1..4] (\i -> map (\j -> (i,j) [i+1..4])

flip simply switches the order of the inputs.

concatMap (\i -> map (\j -> (i,j)) [i+1..4]) [1..4]

And this is how you wind up with Tsuyoshi’s answer.

The second can similarly be desugared into:

concatMap (\i ->
  concatMap (\j ->
    map       (\k ->
      (i,j,k))
    [j+1..6])
  [i+1..6])
[1..6]

More Related Contents:

  1. Zip with default value instead of dropping values?
  2. Merging two lists in Haskell
  3. Understanding a recursively defined list (fibs in terms of zipWith)
  4. Haskell finding mean of cubes of odd members Any ideas? [closed]
  5. Histogram in Haskell [closed]
  6. What is Haskell’s Stream Fusion
  7. Using return vs. not using return in the list monad
  8. Cartesian product of infinite lists in Haskell
  9. Decrementing ranges in Haskell
  10. Lazy lists in Prolog?
  11. Why is lazy evaluation useful?
  12. Replace individual list elements in Haskell?
  13. Using Haskell’s map function to calculate the sum of a list
  14. Need to partition a list into lists based on breaks in ascending order of elements (Haskell)
  15. Haskell Monad – How does Monad on list work?
  16. Is there a function to flatten a nested list of elements?
  17. Removing duplicates from a list in Haskell without elem
  18. Splitting a list of items into two lists of odd and even indexed items
  19. Counting unique elements in a list
  20. Unsequence Monad function within Haskell
  21. Grouping a list into lists of n elements in Haskell
  22. How to check if all of the following items are in a list?
  23. Get number of items from list (or other iterable) with certain condition
  24. Comprehension on a nested iterables?
  25. How to extend a Scala list to enable slicing not by explicit position but by given predicate/condition
  26. Iterate over pairs in a list (circular fashion) in Python
  27. Duplicate elements in a list [duplicate]
  28. Python recursive function to display all subsets of given set
  29. Prevent unlist to drop NULL values
  30. Pythonic way to convert a list of integers into a string of comma-separated ranges

Leave a Comment