Difference between revisions of "99 questions/Solutions/49"
(another solutions using folds) 
m (improve symmetry of foldr/foldl application) 

Line 38:  Line 38:  
gray' :: Integral a => a > [String] 
gray' :: Integral a => a > [String] 

gray' 0 = [""] 
gray' 0 = [""] 

−  gray' n = gl 
+  gray' n = (gl . gr) [] where gl y = foldr (\s acc > ('0':s):acc) y gp 
−  +  gr y = foldl (\acc s > ('1':s):acc) y gp 

−  gp = gray' (n1) 
+  gp = gray' (n1) 
</haskell> 
</haskell> 

Latest revision as of 03:02, 7 June 2021
(**) Gray codes.
An nbit Gray code is a sequence of nbit 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 Nbit Gray code
Solution:
gray :: Int > [String]
gray 0 = [""]
gray n = let xs = gray (n1) in map ('0':) xs ++ map ('1':) (reverse xs)
A similar solution using list comprehension to build the sublists:
gray :: Int > [String]
gray 0 = [""]
gray n = [ '0' : x  x < prev ] ++ [ '1' : x  x < reverse prev ]
where prev = gray (n1)
The Gray code can be recursively defined in the way that for determining the gray code of n we take the Gray code of n1, prepend a 0 to each word, take the Gray code for n1 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.
Another completely different solution (using folds) that is way more efficient, because it needs just the space which is occupied by the list itself:
gray :: Integral a => a > [String]
gray 0 = [""]
gray n = foldr (\s acc > ("0" ++ s):("1" ++ s):acc) [] $ gray (n1)
The key is that the algorithm just crawls one time over the inputlist and uses the (++) operator in a way that it just has a running time of O(1).
Here is another solution using folds that yields the specified result.
gray' :: Integral a => a > [String]
gray' 0 = [""]
gray' n = (gl . gr) [] where gl y = foldr (\s acc > ('0':s):acc) y gp
gr y = foldl (\acc s > ('1':s):acc) y gp
gp = gray' (n1)