How to combine two lists with list comprehension in Haskell?-CodePudding

I would like to combine two lists as with operator . [1,2,3] [4,5,6] = [1,2,3,4,5,6]

So I tried this:

combine2 :: [a] -> [a] -> [a]
combine2 xs ys = [x : ys | x <- xs]

but that is giving me:

a.hs:10:19: error:
    • Occurs check: cannot construct the infinite type: a ~ [a]
    • In the expression: x : ys
      In the expression: [x : ys | x <- xs]
      In an equation for ‘combine2’: combine2 xs ys = [x : ys | x <- xs]
    • Relevant bindings include
        x :: a (bound at a.hs:10:28)
        ys :: [a] (bound at a.hs:10:13)
        xs :: [a] (bound at a.hs:10:10)
        combine2 :: [a] -> [a] -> [a] (bound at a.hs:10:1)
   |
10 | combine2 xs ys = [x : ys | x <- xs]

how to fix that?

CodePudding user response：

The way to fix it is to make it more general. Instead of combine2, write combineN and use it so solve the combine2 problem.

combine2 :: [b] -> [b] -> [b]
combine2 xs ys = combineN [xs,ys]

combineN :: [[b]] -> [b]
combineN ls = [a | l <- ls, a <- l]

We just draw each list from the argument list of lists, and then we draw and produce each element from each list, as if in the inner loop of the two nested loops. In pseudocode:

  for l in ls:
     for a in l:
         produce a

Testing:

> combine2 [1..3] [11..15]
[1,2,3,11,12,13,14,15]

--   l1:      l2:
-- [ [1,2,3], [11,12,13,14,15] ]    -- outer "loop"
-- [  1,2,3 ,  11,12,13,14,15  ]    -- inner "loop"

Or we can see this as putting our lists one under the other in kind of ragged "matrix" and then reading it row by row, element by element:

-- [ [1,2,3] ,         -l1-    [  1,2,3 ,
--   [11,12,13,14,15]  -l2-       11,12,13,14,15
-- ]                           ]

The "rows" are the consecutive values of l in ls = [xs,ys], and the elements in each row are the consecutive values of elements a in each l.

Nested loops are what list comprehensions essentially are.

CodePudding user response：

You are here producing a list of lists, where you prepend ys each time with a value of x. This thus means that if xs is xs = [1,3,0,2] and ys is [1,4,2,5], you constructed a list of lists with [[1, 1, 4, 2, 5], [3, 1, 4, 2, 5], [0, 1, 4, 2, 5], [2, 1, 4, 2, 5]].

You can here work with recursion. Here the base case is that the first list is exhausted. In that case we return the second list, so:

combine2 [] ys = ys

The recursive case is where the first list is not empty and has x as first element, and xs as a (possibly empty) tail. In that case we yield x and recurse on the tail xs:

combine2 (x:xs) ys = x : combine xs ys

If we put these together, we get:

combine2 :: [a] -> [a] -> [a]
combine2 [] ys = ys
combine2 (x:xs) ys = x : combine2 xs ys

We here each time pass ys in the recursive case. Instead of doing that, we can work with a helper function:

combine2 :: [a] -> [a] -> [a]
combine2 zs ys = go zs
    where go [] = ys
          go (x:xs) = x : go xs

CodePudding user response：

Look at the inferred type of your code:

> combine2 xs ys = [x : ys | x <- xs]
> :type combine2
combine2 :: [a] -> [a] -> [[a]]

So you’re returning “list of list of a” when you meant to return “list of a”. The compiler sees that these are both lists, and tries to match the element types, but finds that one contains “list of a” while the other is just “a”. Since the type variable a occurs in the type “list of a”, if they were equal, this would be a sort of infinite loop: a = [a] = [[a]] = [[[a]]] = …, which is almost never what you meant to do, so the typechecker disallows it.

Your code does this:

combine2 [1, 2, 3] [4, 5, 6]
=
[ 1 : [4, 5, 6]
, 2 : [4, 5, 6]
, 3 : [4, 5, 6]
]
=
[ [1, 4, 5, 6]
, [2, 4, 5, 6]
, [3, 4, 5, 6]
]

When you want it to do this:

combine2 [1, 2, 3] [4, 5, 6]
=
[1, 2, 3, 4, 5, 6]

A solution with list comprehensions is to iterate over each list, and then each item within those lists:

combine2' xs ys = [z | zs <- [xs, ys], z <- zs]

In combine2' [1, 2, 3] [4, 5, 6], first zs is set to [1, 2, 3], so z is set to 1, then 2, then 3; then zs is set to [4, 5, 6], so z is set to 4, then 5, then 6.

You can also think of this equationally, in terms of the desugaring of list comprehensions using concatMap:

[z | zs <- [xs, ys], z <- zs]
=
concatMap (\ zs -> concatMap (\ z -> [z]) zs) [xs, ys]
=
concatMap (\ zs -> concatMap pure zs) [xs, ys]
=
concatMap (\ zs -> concat (map pure zs)) [xs, ys]
=
concatMap (\ zs -> zs) [xs, ys]
=
concatMap id [xs, ys]
=
concat (map id [xs, ys])
=
concat [xs, ys]
=
foldr (  ) [] [xs, ys]
=
xs    ys    []
=
xs    ys

Essentially, you are concatenating all of the input lists, where “all” happens to be only 2 in this case.