Recursive Confusion in Haskell

Question

Hope someone helps find out where my mistake is. Call g 3 4 0 2 (M.empty,0) [] , I would expect [[2,1,0,1]] . Instead, I see [[2,1,0,1],[2,1,0,1]] .

It is assumed that the program accumulates various digital figures of length m by adding various numbers to the list, returning back when it reaches n-1 and up when it reaches 0 . An obvious problem occurs in the middle when a function is called recursively for both up and down directions.

If I comment line 11 as follows:

 else gnm (digitCount + 1) (lastDigit + 1) (hash',hashCount') (lastDigit:digits) -- gnm (digitCount + 1) (lastDigit - 1) (hash',hashCount') (lastDigit:digits) 

I get the correct result []

As with commenting out line 11 and changing line 10 to:

 else gnm (digitCount + 1) (lastDigit - 1) (hash',hashCount') (lastDigit:digits) 

And again the correct result [[2,1,0,1]]

Why, when I call g twice with the ++ operator, do I get two [2,1,0,1] instead of one? In my opinion, each result in g should be different, because in any recursive call, another order accumulates (or should) accumulate.

Thanks in advance.

 import qualified Data.Map as M g :: Int -> Int -> Int -> Int -> (M.Map Int Bool, Int) -> [Int] -> [[Int]] gnm digitCount lastDigit (hash,hashCount) digits | digitCount == m = if test then [reverse digits] else [] | otherwise = if lastDigit == 0 then gnm (digitCount + 1) (lastDigit + 1) (hash',hashCount') (lastDigit:digits) else if lastDigit == n - 1 then gnm (digitCount + 1) (lastDigit - 1) (hash',hashCount') (lastDigit:digits) else gnm (digitCount + 1) (lastDigit + 1) (hash',hashCount') (lastDigit:digits) ++ gnm (digitCount + 1) (lastDigit - 1) (hash',hashCount') (lastDigit:digits) where test = hashCount == n (hash',hashCount') = if test then (M.empty,hashCount) else case M.lookup lastDigit hash of Just anyting -> (hash,hashCount) Nothing -> (M.insert lastDigit True hash,hashCount + 1) 

Answer 1

Why, when I call g twice using the ++ operator, do I get two [2,1,0,1] instead of just one? In my opinion, each result in g should be different, because with any recursive call, a different order of digits (or should be) accumulate.

But your pair (Map, Int) is the same in both calls, so recursive calls don't know what was found by the other call. Consider calling g ... (lastDigit-1). It will also call g ... (lastDigit) (adding 1 to (lastDigit-1) that it got) and follow the branch g ... (lastDigit + 1) to get the same result.

Also, (Map a ()) is (Set a), and since you are not using the Bool value on the map, this is the same as ():

  import qualified Data.Set as S g :: Int -> Int -> Int -> Int -> (S.Set Int, Int) -> [Int] -> [[Int]] gnm digitCount lastDigit (hash,hashCount) digits | digitCount == m = if test then [reverse digits] else [] | lastDigit < 0 || lastDigit == n = [] | otherwise = gnmd' (lastDigit + 1) h' (lastDigit:digits) ++ gnmd' (lastDigit - 1) h' (lastDigit:digits) where test = hashCount == n d' = digitCount + 1 h' | test = (S.empty,hashCount) | S.member lastDigit hash = (hash,hashCount) | otherwise = (S.insert lastDigit hash,hashCount + 1) 

Answer 2

Now that you have a job, here is a more general approach.

We need to go through the decision tree.

  data S a = Solution a | Explore [S a] 

Decisions are the leaves of this tree. Explore the list of options.

  -- this is very much unfoldr-like generator :: [S a] -> [a] generator [] = [] generator (Solution a: ss) = a: generator ss generator (Explore ps: ss) = generator $ ss ++ ps 

Now, given the list of "possible solutions", create a list of solutions. Generator Sample Pattern Explores and adds a list of learning solutions to the bottom of the list. Thus, we study solutions in the first place, and thus we can deal with non-limiting branches. (The depth of the first cannot leave the intransitive branches). This, of course, is at the expense of memory, but you can find a finite number of solutions even for problems with an infinite number of solutions.

Now the function that generates the solutions for your problem:

  g :: Int -> Int -> [S [Int]] gnm = [Explore $ g' [i] (S.singleton i) | i <- [1..n-1]] where g' is@ (h:_) ms | h < 0 || h >= n || length is > m = [] --no solution, nothing to explore | otherwise = maybeSolution ++ [ Explore $ g' ((h-1):is) $ S.insert (h-1) ms , Explore $ g' ((h+1):is) $ S.insert (h+1) ms ] where maybeSolution | S.size ms == n = [Solution is] | otherwise = [] 

Given n and m, it produces an Explore subtree list. g 'is a helper function that creates a list of subtrees, given the list of already created Int and the set of Int already in use. Thus, there is a certain termination condition: we added a number outside the required range, or the list became too long - studying any additional results cannot lead to Solutions, so return []. Otherwise, we are within the limits, perhaps Solution sees that the Ints list is already a valid solution and offers more subtrees for study.

  main = print $ map reverse $ generator $ g 3 6 

Your problem has been resolved.

Answer 3

In two recursive calls to g combined with (++) in the last else branch, you pass exactly the same parameters except lastDigit .

The base register of your recursion does not look at lastDigit - it just compares m and digitCount , n and hashCount , and then returns [reverse digits] .

Thus, in any situation when a case (++) immediately occurs, followed by a base register returning [reverse digits] , you will get a repeated value.

I did not fully understand your specification of the problem, but perhaps you need to add the “new” value for lastDigit to the digits when you make recursive calls, i.e. (lastDigit-1):digits or (lastDigit+1):digits .