CODEWITHSUNDEEP
haskell
akonsu
akonsu

Reputation: 29538

how does liftM (:[]) work

I am trying to understand the expression below. It converts the list of characters ['a','b','c'] to a list of strings ["a", "b", "c"]

liftM (:[]) "abc"

How does this happen?

Upvotes: 6

Views: 979

Answers (4)

duplode
duplode

Reputation: 34378

liftM is equivalent to fmap, only specialised to monads. (:[]) uses (:) to make a function that produces lists of one element. Just like (+2) is a compact way of writing (\x -> x + 2), (:[]) is equivalent to (\x -> x : []), or (\x -> [x]).

Your expression, then, might have been written as:

fmap (\x -> [x]) "abc"

The existence of liftM reflects the fact that any legitimate Monad can be made into a Functor by doing fmap f m = m >>= \x -> return (f x). You can always replace liftM by fmap, so the only reasons to use it are:

  • to define fmap for free if you already have a Monad instance (and don't want to use the DeriveFunctor GHC extension), and

  • an entirely optional style choice (if you are writing obviously monadic code and feel that liftM looks better than fmap).

Upvotes: 8

Cactus
Cactus

Reputation: 27626

The robotic monkey head operator (:[]) is just the section of the list cons (:) and the empty list [], i.e. (:[]) is equivalent to (\x -> x:[]); which in turn can also be written using list syntax as (\x -> [x]).

Rewritten this way, we have

liftM (\x -> [x]) "abc"

The string literal "abc" is also just syntax sugar for the character list ['a', 'b', 'c'], so we can in turn rewrite the above as

liftM (\x -> [x]) ['a', 'b', 'c']

liftM is just fmap from the Dark Days when Functor wasn't a superclass of Monad, giving

fmap (\x -> [x]) ['a', 'b', 'c']

The Functor instance of [] sets fmap = map, giving

map (\x -> [x]) ['a', 'b', 'c']

which reduces to 

[['a'], ['b'], ['c']]

Or, going back to string notation

["a", "b", "c"]

Q.e.d.

Upvotes: 14

melpomene
melpomene

Reputation: 85757

liftM is defined as:

liftM f m = m >>= \x -> return (f x)

We're using liftM with a list (of characters), so we need to look at the list instance of Monad to see how >>= and return are defined:

instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)

Thus

liftM f xs = xs >>= \x -> return (f x)
           = concat (map (\x -> [f x]) xs)

The concat on the outside and the [ ] on the inside cancel each other out, so

liftM f xs = map (\x -> f x) xs
           = map f xs

In other words, liftM in the list monad is simply map.

map (:[]) ['a', 'b', 'c'] = [(: []) 'a', (: []) 'b', (: []) 'c']
                          = ['a' : [], 'b' : [], 'c' : []]
                          = [['a'], ['b'], ['c']]
                          = ["a","b","c"]

because a string is really just a list of characters.

Upvotes: 6

aemxdp
aemxdp

Reputation: 1339

Function liftM turns a function which takes input and produces output to a function which takes input in some monad and produces output in the same monad. Lets look at its definition:

liftM :: Monad m => (a -> b) -> m a -> m b
liftM f mx = mx >>= \x -> return (f x)

Strings in Haskell are lists of characters (type String = [Char]), so

"abc" = ['a', 'b', 'c'] :: [Char]

From your application compiler infers a = Char, b = [Char], m a = [Char], m = []. So m b = [[Char]] = [String]. List is a monad where return x = [x] and (>>=) = concatMap. So if we specialize above definition we get:

liftM f mx = concatMap (\x -> [f x]) mx

And if we apply the arguments we get:

concatMap (\x -> [[x]]) ['a', 'b', 'c'] =
concat $ map (\x -> [[x]]) ['a', 'b', 'c'] =
concat $ [[['a']], [['b']], [['c']]] =
[['a'], ['b'], ['c']] =
["a", "b", "c"]

Upvotes: 12

Related Questions