how to generate all possible palindromes of the length n?
the only chars ['a'..'z'] should be used
palindrome n :: Integer -> [String]
Lets for simplicity first assume that n is even, later we can generalize the function. We can use recursion for that. We define a helper function pal' :: Integer -> [String] -> [String]. Here the second argument, is the accumulated reverse string. So once we hit 0, we simply have to emit a single list the contain the accumulated reversed string, like:
pal' 0 r = [r]
Given however we are still in the generating part of the palindrome, the left side thus, we can use list comprehension, like:
pal' k r = [ c : p | c <- ['a'..'z'], p <- pal' (k-1) (c:r) ]
So we iterate over [a..z] and for each such character, we we perform a recursive call on pal' where we need to generate an additional k-1 characters, with (c:r) as reversed string to be emitted. Furthermore we yield for these palindromes c : p. We put thus the choses character in front of the palindrome.
So now for an even_palindrome function that generates even palindromes, we can write:
evenpalindrome :: Integer -> [String]
evenpalindrome n = pal' (div n 2) []
where pal' 0 r = [r]
pal' k r = [ c : p | c <- ['a'..'z'], p <- pal' (k-1) (c:r) ]
For testing purposes, I set the code to pick from the range `c <- ['a'..'d'], but you can set it to any range you want.
And if we generate palindromes for length 0, 2 and 4, we get:
*Main> evenpalindrome 0
[""]
*Main> evenpalindrome 2
["aa","bb","cc","dd"]
*Main> evenpalindrome 4
["aaaa","abba","acca","adda","baab","bbbb","bccb","bddb","caac","cbbc","cccc","cddc","daad","dbbd","dccd","dddd"]
So that seems to work. If we however write evenpalindrome 1, it will work in the sense that it will take integer division, and thus generate palindromes for length 0.
Now the question is what do we have to alter in order to let it work for odd length. There are two things that need to change here:
div n 2, but div (n+1) 2; andSo it means that we should first check n modulo 2 (let that be d), and then rewrite:
pal' 0 r = [drop (fromInteger d) r]
Furthermore as said before we should call the initial pal' with pal' (div (n+1) 2) [], so now the generalized version is:
palindrome :: Integer -> [String]
palindrome n = pal' (div (n+1) 2) []
where pal' 0 r = [drop (fromInteger d) r]
pal' k r = [ c : p | c <- ['a'..'z'], p <- pal' (k-1) (c:r) ]
d = mod n 2
Which produces:
*Main> palindrome 1
["a","b","c","d"]
*Main> palindrome 2
["aa","bb","cc","dd"]
*Main> palindrome 3
["aaa","aba","aca","ada","bab","bbb","bcb","bdb","cac","cbc","ccc","cdc","dad","dbd","dcd","ddd"]
*Main> palindrome 4
["aaaa","abba","acca","adda","baab","bbbb","bccb","bddb","caac","cbbc","cccc","cddc","daad","dbbd","dccd","dddd"]
*Main> palindrome 5
["aaaaa","aabaa","aacaa","aadaa","ababa","abbba","abcba","abdba","acaca","acbca","accca","acdca","adada","adbda","adcda","addda","baaab","babab","bacab","badab","bbabb","bbbbb","bbcbb","bbdbb","bcacb","bcbcb","bcccb","bcdcb","bdadb","bdbdb","bdcdb","bdddb","caaac","cabac","cacac","cadac","cbabc","cbbbc","cbcbc","cbdbc","ccacc","ccbcc","ccccc","ccdcc","cdadc","cdbdc","cdcdc","cdddc","daaad","dabad","dacad","dadad","dbabd","dbbbd","dbcbd","dbdbd","dcacd","dcbcd","dcccd","dcdcd","ddadd","ddbdd","ddcdd","ddddd"]
A nice thing about constructing the reverse part using recursion that way, is that the second half of all the palindromes is stored more efficiently. Given we generate palindromes of length 5 for the `['a'..'b'] range, the final list (after complete evaluation), will look like:
+---+ | o--- 'a' -- 'a' -> 'a' -\ +---+ > 'a' -\ | o--> 'a' -> 'a' -> 'b' -/ \ +---+ > 'a' | o--> 'a' -> 'b' -> 'a' -\ / +---+ > 'b' -/ | o--> 'a' -> 'b' -> 'b' -/ +---+ | o--> 'b' -> 'a' -> 'a' -\ +---+ > 'a' -\ | o--> 'b' -> 'a' -> 'b' -/ \ +---+ > 'b' | o--> 'b' -> 'b' -> 'a' -\ / +---+ > 'b' -/ | o--> 'b' -> 'b' -> 'b' -/ +---+