The questions regarding my first haskell program
The program return all possible combinations of '0' and '1' length N.
addToElement :: String -> String -> String
addToElement element symbol = element ++ symbol
addOneToElement :: String -> String
addOneToElement element = addToElement element "1"
addZeroToElement :: String -> String
addZeroToElement element = addToElement element "0"
processListOnce :: [String] -> [String]
processListOnce lst = do
let s1 = map addOneToElement lst
let s2 = map addZeroToElement lst
s1 ++ s2
processList :: [String] -> Integer -> [String]
processList lst 1 = processListOnce lst
processList lst n = do
let tmp = processListOnce(lst)
processList tmp (n - 1)
{-
processList2 :: [String] -> Integer -> [String]
processList2 lst n = iterate (map processListOnce) lst !! n
-}
main = do
let s = processList ["0", "1"] 2
let ss = show s
putStrLn ss
It is my first Haskell program so I will be thankful if you help me:
First of all pls refactore my code Haskell-way. I already know one magic refactring:
Control.Monad.replicateM n [0,1]
but this solution is not good for studying purposes :)
Why I can not use ProcessList2 instead ProcessList and get error:
all_possible_combinations.hs:44:51: Couldn't match expected type `[Char]' against inferred type `Char' Expected type: [String]] Inferred type: [String] In the second argument of `iterate', namely 开发者_StackOverflow社区`lst' In the first argument of `(!!)', namely `iterate (map processListOnce) lst'
Is there any way to skip (not use) the 'tmp' variable in the processList? I have tried, but got the error:
processList :: [String] -> Integer -> [String] processList lst 1 = processListOnce lst processList lst n = processList processListOnce(lst) (n - 1) all_possible_combinations.hs:39:32: Couldn't match expected type `[String]' against inferred type `[String] -> [String]' In the first argument of `processList', namely `processListOnce' In the expression: processList processListOnce (lst) (n — 1) In the definition of `processList': processList lst n = processList processListOnce (lst) (n — 1)
Thanks in advance.
First of all pls refactore my code Haskell-way. I already know one magic refactring:
Control.Monad.replicateM n [0,1]
but this solution is not good for studying purposes :)
Actually, while I certainly wouldn't expect someone new to Haskell to come up with such a solution, I think that understanding this version would be very good for studying purposes.
The regular replicate
function is pretty simple: It creates a list of the same element repeated some number of times. This is also the first step of what replicateM
does:
> replicate 2 ["0", "1"]
[["0", "1"], ["0", "1"]]
The second step of what replicateM
does is "sequence" the list according to the Monad
of the elements, turning something a list of monadic values [m a]
into a monadic list of values m [a]
. What this does is "combine" the structure of each monadic value in some sense, where the specific meaning of "combine" depends on the specific monad.
As a Monad
, lists represent something like trying multiple possibilities. So when we "sequence" the values, that means that at each step, every possibility is tried separately, and all possible results are collected.
So, ["0", "1"]
is a monadic value representing trying two different possibilities. [["0", "1"], ["0", "1"]]
is a list of that monadic value repeated twice. To sequence that list, we take each possibility from the first element of the list, use it as the head of the result list, then continue until reaching the end. Because each group of possibilities is the same, the final result is all the possible combinations of each possible item:
> replicateM 2 ["0", "1"]
[["0","0"],["0","1"],["1","0"],["1","1"]]
About making it Haskelly, here is a solution that is not pure magic (as the replicateM may be)
onesAndZeroes 0 = [[]]
onesAndZeroes n = [x:xs | x <- [0,1], xs <- onesAndZeroes (n-1)]
Since you are new to haskell, if you don't understand it, it might help to read about list comprehensions.
Is there any way to skip (not use) the 'tmp' variable in the processList? I have tried, but got the error:
This definition has used the wrong precedence. You should write
processList lst n = processList (processListOnce lst) (n - 1)
-- # ^ ^
Why I can not use ProcessList2 instead ProcessList and get error:
processListOnce
is already a [String] -> [String]
function. If you use map processListOnce
it will become a [[String]] -> [[String]]
function. Thus, remove the map
.
processList2 lst n = iterate processListOnce lst !! n
Another solution:
onesAndZeroes n = combo n ["0", "1"]
where combo 1 cs = cs
combo n cs = combo (n-1) (f cs)
f = concatMap (\x -> ['0':x, '1':x])
Like others I think replicateM would be my first choice, but if I was to avoid that this would be my solution. Perhaps less clear/concise than the list comprehension solution, but I find tail call recursion quite elegant.
精彩评论