99 questions/Solutions/49
From HaskellWiki
(Difference between revisions)
(another solution using list comprehension) |
|||
| Line 15: | Line 15: | ||
</haskell> | </haskell> | ||
| - | + | A similar solution using list comprehension to build the sub-lists: | |
| - | + | ||
| + | <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.
