Personal tools

99 questions/Solutions/49

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
 
(another solution using list comprehension)
Line 15: Line 15:
 
</haskell>
 
</haskell>
   
It seems that the Gray code can be recursively defined in the way that for determining the gray code of n we take the Gray code of n-1, prepend a 0 to each word, take the Gray code for n-1 again, reverse it and prepend a 1 to each word. At last we have to append these two lists.
+
A similar solution using list comprehension to build the sub-lists:
(The [http://en.wikipedia.org/wiki/Gray_code Wikipedia article] seems to approve this.)
+
  +
<haskell>
  +
gray :: Int -> [String]
  +
gray 0 = [""]
  +
gray n = [ '0' : x | x <- prev ] ++ [ '1' : x | x <- reverse prev ]
  +
where prev = gray (n-1)
  +
</haskell>
  +
  +
The Gray code can be recursively defined in the way that for determining the gray code of n we take the Gray code of n-1, prepend a 0 to each word, take the Gray code for n-1 again, reverse it and prepend a 1 to each word. At last we have to append these two lists. For more see [http://en.wikipedia.org/wiki/Gray_code the Wikipedia article].

Revision as of 21:58, 17 July 2010

(**) Gray codes.

An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. Find out the construction rules and write a predicate with the following specification:

% gray(N,C) :- C is the N-bit Gray code

Solution:

gray :: Int -> [String]
gray 0 = [""]
gray n = let xs = gray (n-1) in map ('0':) xs ++ map ('1':) (reverse xs)

A similar solution using list comprehension to build the sub-lists:

gray :: Int -> [String]
gray 0 = [""]
gray n = [ '0' : x | x <- prev ] ++ [ '1' : x | x <- reverse prev ]
  where prev = gray (n-1)

The Gray code can be recursively defined in the way that for determining the gray code of n we take the Gray code of n-1, prepend a 0 to each word, take the Gray code for n-1 again, reverse it and prepend a 1 to each word. At last we have to append these two lists. For more see the Wikipedia article.