Haskell: Concatenating Lists without using (++)

Question

I am trying to write a function that will combine 2 lists without using "divide and conquer". Therefore I cannot use (++).

Prelude> let combineList (x:xs) (y:ys) = if null (y:ys)==True then x:xs else combineList (x:xs++[y]) (ys)

This is what I have right now, and I get "Non-exhaustive patterns in function combineList". I realize that the problem comes from if null (y:ys)==True, because this function works -

Prelude> let combineList (x:xs) (y:ys) = if ys==[] then x:xs++[y] else combineList (x:xs++[y]) (ys)

but I'd like to get rid of the ++[y] in the output if possible.

Correction to the code is much appreciated.

I'm not sure I understand what you're asking for. Your combineList should basically do what ++ does, but it shouldn't use ++ to achieve this? — us2012
– us2012, Commented Oct 1, 2013 at 0:36
Sorry Daniel, it's only my second class in computer science, I'm not sure if i know what the source means as I've only learned how to do things on one line. Correction to my code would be appreciated. — Iceandele
– Iceandele, Commented Oct 1, 2013 at 0:47

muhmuhten · Accepted Answer · 2013-10-05 00:35:39Z

(x:xs) does not match any list. Rather, it matches a list with a head element x and a tail xs. (You could sort of think of it as matching a cons cell, I guess.) null (x:xs) also can't ever be false, because any (x:xs) is not null, basically by definition.

"Non-exhaustive patterns in function" means the input could not be matched to a pattern for the function. In this case, neither argument can be null, so if either is null, you will have a match failure.

Since you're apparently doing it with ifs, you'll want to match any list, so the function will look like

combineList xs ys = if null xs then ys else head xs : combineList (tail xs) ys

A more usual way to do this in haskell, however, would be to pattern-match against the nil pattern separately:

cl [] ys = ys
cl (x:xs) ys = x : cl xs ys

(this is equivalent to the definition of (++), but in prefix form:)

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

It also follows the fold pattern: we can accumulate consing over the first list, with the second list used as the initial tail:

cl' xs ys = foldr (:) ys xs

This also allows us to write the function pointlessly (i.e. in pointfree style):

cl'' = flip (foldr (:))

Will Ness · Accepted Answer · 2013-10-04 08:02:43Z

1

The warning "Non-exhaustive patterns in function `combineList`" means that your function doesn't pattern match every constructor of the data type. List type contains two constructors, (:) and []; when you use pattern matching the compiler assumes that you want to match every constructor of the data type.

Here is one possible solution:

combineList (x:xs) ys = if null xs then x : ys else x : combineList xs ys

In Haskell a better way to write this is using pattern matching. Note that this is also the actual definition of (++):

combineList []     ys = ys 
combineList (x:xs) ys = x : combineList xs ys

edited Oct 4, 2013 at 8:02

Will Ness

71.6k10 gold badges105 silver badges192 bronze badges

answered Oct 1, 2013 at 1:04

Rodrigo Taboada

2,7054 gold badges27 silver badges27 bronze badges

Collectives™ on Stack Overflow

Haskell: Concatenating Lists without using (++)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related