Haskell, List as input for a function, How?

Question

I've been given the following question in my coursework;

Define a function

flatten :: [(Char,Int)] -> String

that flattens a list of pairs of characters and digits to a string. For example:

flatten [('a',5),('b',4),('c',2)]
"a5b4c2"
flatten [('d',9),('d',3)]
"d9d3"

My problem is that whenever I attempt to define this function i get a type error relating the the [(Char, Int)] input. For example;

Couldn't match type '(Char, Int)' with '[Char]'
Expected type: [[Char]]
Actual type: [(Char, Int)]

I've tried more ways of writing this definition in more ways than I can count, so I don't have any particular code to show, or any particular error ( I kept getting different ones...so many). All i have so far is;

flatten :: [(Char, Int)] -> String
flatten [] = []

i figure my next line should go something like;

flatten ???? = concat (????)

but I have no idea what to put in place of these question marks and Google search/class notes give no examples to follow. any ideas?

willeM_ Van Onsem · Accepted Answer · 2017-03-29 12:19:18Z

4

Well it is clear that in the case the list is not empty, it is of the form ((ca,cb):cs) with ca the Char, cb the Int and cs the remainder of the list [(Char,Int)].

In that case we can simply construct a string for that sequence ca:(show cb) with show :: Show a => a -> String we convert an integer to its String counterpart. Next we concatenate the flattening of remainder of the list to that string, so:

flatten ((ca,cb):cs) = ca:(show cb ++ flatten cs)

Or in full:

flatten :: [(Char, Int)] -> String
flatten [] = []
flatten ((ca,cb):cs) = ca:(show cb ++ flatten cs)

answered Mar 29, 2017 at 12:19

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Zeta · Accepted Answer · 2017-03-29 13:50:56Z

3

First of all, we try to create a String from a (Char, Int). If we can do that we've almost done, since we can do that for all (Char, Int). So let's transform a single (Char, Int):

flattenSingle :: (Char, Int) -> String
flattenSingle (c, i) = c : show i

Now, we need to do that for all entries:

flattenAll :: [(Char, Int)] -> [String]
flattenAll xs = map flattenSingle xs

And last, but not least, we need to concat the [String] (which is a [[Char]]) to a String (which is a [Char]):

flatten :: [(Char, Int)] -> String
flatten xs = concat (flattenAll xs)

And we're done. How did we do that? Well, we've started with a much easier problem, namely how to get a single String from a (Char, Int), and used that to get our result.

Here's everything in a single function:

flatten = concat . map flattenSingle
  where
    flattenSingle (c, i) = c : show i

Since concat . map f is often used, there's a function for that, called concatMap:

flatten :: [(Char, Int)] -> String
flatten = concatMap flattenSingle
  where
    flattenSingle (c, i) = c : show i

answered Mar 29, 2017 at 13:50

Zeta

106k13 gold badges206 silver badges250 bronze badges

1 Comment

Redu Over a year ago

+ for the concatMap my original idea was flatten = concat.map (\(c,i) -> c : show i)

ƛƛƛ · Accepted Answer · 2017-03-29 15:32:58Z

2

Let’s think about what goes into flatten and what comes out of it. flatten, takes a list of pairs of type: (Char, Int) and produces a [Char]; it produces a list from an existing list. Does this ring a bell?

flatten xs = [ c | (char, int) <- xs, c <-[char] ++ show int]

We can sequentially deconstruct each pair in the given list; for each pair, we turn each component into a string so we can concatenate them. Now we have a string for each pair, we just need to take each character out to produce the final string.

answered Mar 29, 2017 at 15:32

ƛƛƛ

8927 silver badges11 bronze badges

Comments

user12457 · Accepted Answer · 2017-03-29 21:02:32Z

1

flatten = mconcat. map (\(c,i) -> [c] ++ show i)

answered Mar 29, 2017 at 21:02

user12457

2911 silver badge4 bronze badges

Comments

Aleph0 · Accepted Answer · 2017-03-30 06:07:01Z

1

You might also use foldl to make your intention very clear:

a=[('a',5),('b',4),('c',2)]
f b (x,y)=b++[x]++(show y)   
result=foldl f "" a

Or you can make it a one-liner:

Solution 1:

foldl (\b (x,y)->b++[x]++(show y)) "" a

Solution 2:

concat $ map (\(x,y)->[x]++show y) a

Solution 3: (Being more efficient compared to solution 1)

foldr (\(x,y) b->b++[x]++(show y)) "" a

edited Mar 30, 2017 at 6:07

answered Mar 29, 2017 at 12:37

Aleph0

6,1047 gold badges42 silver badges100 bronze badges

2 Comments

amalloy Over a year ago

foldr would be acceptable here (though concatMap is better, as mentioned elsewhere). foldl, however, is a poor choice. It is quite expensive to use in this way.

Aleph0 Over a year ago

Thanks for the hint.

Collectives™ on Stack Overflow

Haskell, List as input for a function, How?

5 Answers 5

Comments

1 Comment

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

1 Comment

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related