CODEWITHSUNDEEP
haskell
elliptic00
elliptic00

Reputation: 447

Merge two lists with alternative elements in Haskell

I'm new Haskell and try to practice my Haskell skill.

I want to implement a function to merge two lists so that the items are alternative from each list.

["a", "b", "c"]
["1", "2", "3"]

After the merger.

["a", "1", "b", "2", "c", "3"]

Here is my Haskell code

mergeList::[String]->[String]->[String]
mergeList [] [] = []
mergeList  _ [] = []
mergeList [] _  = []
mergeList (x:xs) (y:ys) = x:y:mergeList xs ys

The code works as long as the lengths of two lists are the same.

But I want to have some error checking on the lengths of the two lists.

If the length of two lists are different, then I want to report an error.

mergeList::[String]->[String]->[String]
mergeList l r | length l /= length r = error "report an error"
              | otherwise =

How can I finish the otherwise section?

Upvotes: 1

Views: 2357

Answers (5)

Randomize
Randomize

Reputation: 9103

Your otherwise function it might be something like this:

otherwise = reverse $ foldl (\a (x,y) -> x:y:a) [] (x `zip` y)

Example:

Prelude> let y = ["a", "b", "c"]
Prelude> let x = ["1", "2", "3"]
Prelude> reverse $ foldl (\a (x,y) -> x:y:a) [] (x `zip` y)
["a","1","b","2","c","3"]

or the elliptic00 solution with foldr that avoids the usage of the reverse:

 otherwise = foldr ((x, y) a -> x:y:a) [] (x `zip` y)

Upvotes: 1

dfeuer
dfeuer

Reputation: 48581

luqui points out that we like to be safe in Haskell, avoiding error. But waiting till we get to the end of at least one list before yielding anything throws away any hope of laziness. One option is to toss error handling to the caller. We can fake up lists like this:

import Data.Bifunctor
import Data.Bifunctor.Fix
import Data.Bifunctor.Tannen

data ListF l a = NilF | ConsF a l

instance Bifunctor ListF where
  bimap _ _ NilF = NilF
  bimap f g (ConsF a l) = ConsF (f a) (g l)

{-instance Bifoldable ListF where ...

instance Bitraversable ListF where ... -}

type List = Fix ListF

But we can add in error handling:

type EList e = Fix (Tannen (Either e) ListF)

An EList e a is either an error of type e, a NilF or a ConsF holding an a and another EList e a.

This composition approach, however, ends up being very verbose, confusing, and somewhat inefficient. A better approach in practice is to use a totally custom list type:

data EList' e a = Error e | Nil | Cons a (EList' e a)

Upvotes: 0

denys.fridman
denys.fridman

Reputation: 165

In your pattern matching raise an error if EXACTLY one of the lists is empty. So you would have

mergeList (x: xs) (y: ys) = x: y: mergeList xs ys
mergeList []      []      = []
mergeList _       _       = error "your error"  -- falling through to this pattern means that exactly one of the lists is empty

It is somewhat redundant to check whether lengths of 2 lists are equal, since 'length' has O(n) complexity, meaning that you would go over lists twice (in a case of equal lengths).

As luqui correctly pointed out, there are more elegant ways to solve the problem using Maybe type. When you learn about functors (and Maybe is an instance of class Functor), you could write:

mergeList :: [a] -> [a] -> Maybe [a]
mergeList (x: xs) (y: ys) = fmap (\rest -> x: y: rest) $ mergeList xs ys
mergeList []      []      = Just []
mergeList _       _       = Nothing

Upvotes: 2

Carcigenicate
Carcigenicate

Reputation: 45736

The easiest way would probably just to do a check beforehand, then route the main work to an auxiliary function:

mergeList::[String]->[String]->[String]
mergeList xs ys
    | length xs /= length ys = error "Lists must be the same length" 
    | otherwise go xs ys
    where
        go [] [] = []
        go  _ [] = []
        go [] _  = []
        go (x:xs) (y:ys) = x:y:go xs ys

The check is done in the main function, and if the list's are the same size, they're handed to an internal function that does the main processing. Note how go is just your original function; it's just been internalized within a wrapper function. You could use a more descriptive name than go; I was trying to keep it brief.

It's been awhile since I've written Haskell, so I apologize for any syntax issues.

You could also generalize the function by changing the signature to:

mergeList::[a]->[a]->[a]

Since you're not doing anything specific to Strings in the function.

Upvotes: 2

luqui
luqui

Reputation: 60463

Using error is discouraged. In Haskell we like to define our functions for all possible inputs, so that the type system can guide us to write correct programs. If your function is invalid for lists of different lengths, one way would be to use Maybe.

mergeList :: [a] -> [a] -> Maybe [a]
mergeList [] [] = Just []
mergeList (x:xs) (y:ys) =
    case mergeList xs ys of
        Just merged -> Just (x:y:merged)
        Nothing     -> Nothing
mergeList _ _ = Nothing

There are more succinct ways to write this, but I'm staying near the ground floor.

Now users of mergeList are required to define what to do in the case that they passed lists of two different lengths.

Upvotes: 8

Related Questions