I want to know how the map this function works in Haskell

user_14513373 0
Viewed 143
bools :: Int -> [[Bool]]
bools 0 = [[]]
bools n = map (False:) bss ++ map (True:) bss
    where bss = bools (n-1)

Enter the following and the result is...

bools 2

[[False,False],[False,True],[True,False],[True,True]]

I'm not sure what the '(False :)' and '(True :)' means in this function.

And I'm not sure why the results come out like that.

There is no article explaining Haskell in detail, so ask a question here.

Thanks for answering my problem.

haskell
1 Answers

The "cons" function (:) is one of the data constructors of a list. Haskell implements lists like a linked list. A list has two data constructors:

  1. the empty list []; and
  2. the cons [wiki] that takes an element which is the head of the list, and another list of elements which is the tail of the list.

So a list like [1,4,2] is the "short form" of 1 : (4 : (2 : [])), or in canonical form (:) 1 ((:) 4 ((:) 2 [])).

With the section of an infix operator [haskell-wiki], we can write functions like (1 :) which is short for (:) 1.

The (False :) expression is thus short for (:) False. It is a function that takes a list of Bools, and returns a list that starts with False followed by the elements of the given list. (True :) on the other hand will prepend the list with True.

If you thus call bools 2, then this will evaluate to:

bools 2 = map (False :) bss ++ map (True :) bss
    where bss = bools 1

here bools 1 will evaluate to:

bools 1 = map (False :) bss ++ map (True :) bss
    where bss = bools 0

and the first clause of the bools function specifies that bools 0 = [[]], so that means that bools1 is:

bools 1 = map (False :) [[]] ++ map (True :) [[]]

this is thus equal to:

bools 1 = [[False]] ++ [[True]]

and thus:

bools 1 = [[False], [True]]

for bools 2, we thus obtain:

bools 2 = map (False :) [[False], [True]] ++ map (True :) [[False], [True]]

we thus prepend False to the lists in the map (False :) expression, and we prepend True to the lists in the map (True :) expression:

bools 2 = [[False, False], [False, True]] ++ [[True, False], [True, True]]

which is thus equal to:

bools 2 = [[False, False], [False, True], [True, False], [True, True]]
user_675790
Related