递归混淆在Haskell中 [英] Recursion confusion in Haskell

问题描述

我希望有人能帮忙弄清楚我的错误在哪里。调用 g 3 4 0 2（M.empty，0）[] ，我期待 [[2,1,0,1]] 作为结果。相反，我看到 [[2,1,0,1]，[2,1,0,1]] 。

该程序应该通过每次向列表添加一个不同的数字来累积长度 m 的不同数字模式，当达到 n-1 时返回，当达到 0 时返回。在向上和向下两个方向递归调用函数时，明显的问题发生在中间。

如果我像第11行那样注释掉：

  else gnm （digitCount + 1）（lastDigit + 1）（hash'，hashCount'）（lastDigit：digits）
  -  gnm（digitCount + 1）（lastDigit  -  1）（hash'，hashCount'）（lastDigit：digits ）
  

我得到正确的结果 []

在将第11行和第10行修改为：

  else gnm（digitCount + 1）（lastDigit  -  1）（hash'，hashCount'）（lastDigit：digits）
  

同样，一个正确的结果 [[2,1,0,1]]

使用 ++ 运算符调用 g 两次，我得到两个 [2,1 ，0,1] 的而不是一个？在我看来， g 中的每个结果都应该是不同的，因为在任何递归调用中，不同的数字顺序是（或应该是）累积的。

提前致谢

 导入限定的Data.Map为M 
 
g :: Int  - > Int  - > Int  - > Int  - > （M.Map Int Bool，Int） - > [Int]  - > [[Int]] 
 g n m digitCount lastDigit（hash，hashCount）数字
 | digitCount == m = if test then [reverse digits] else [] 
 |否则= 
 if lastDigit == 0 
然后gnm（digitCount + 1）（lastDigit + 1）（hash'，hashCount'）（lastDigit：digits）
 else if lastDigit == n  - 1 
然后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'）= 
如果测试
则（M.empty，hashCount）
 else case M.lookup 
的lastDigit哈希值只是anyting  - > （hash，hashCount）
 Nothing  - > （M.insert lastDigit True hash，hashCount + 1）
  

解决方案

为什么在使用++运算符调用g两次时，我得到两个[2,1,0,1]而不是
一个？在我看来，g中的每个结果都应该是不同的，因为在任何递归调用中，
不同的数字顺序是（或者应该是）累积的。

但是你的一对（Map，Int）在两次调用中都是相同的，所以递归调用不知道其他调用发现了什么。考虑调用g ...（lastDigit-1）。它也会调用g ...（lastDigit）（通过给（lastDigit-1）添加1得到），然后按照分支g ...（lastDigit + 1）产生相同的结果。

另外，（Map a（））是一个（Set a），并且由于您不使用映射中的布尔值，所以它与（）相同：

 将限定的Data.Set设置为S 
 
g :: Int  - > Int  - > Int  - > Int  - > （S.Set Int，Int） - > [Int]  - > [[Int]] 
 g n m digitCount lastDigit（hash，hashCount）数字
 | digitCount == m = if test then [reverse digits] else [] 
 | lastDigit< 0 || lastDigit == n = [] 
 |否则= gnm d'（lastDigit + 1）h'（lastDigit：digits）
 ++ gnm d'（lastDigit  -  1）h'（lastDigit：digits）
 where test = hashCount == n 
 d'= digitCount + 1 
 h'
 | test =（S.empty，hashCount）
 | S.member lastDigit hash =（hash，hashCount）
 |否则=（S.insert lastDigit hash，hashCount + 1）
  

I hope someone can help figure out where my error lies. Calling g 3 4 0 2 (M.empty,0) [], I would expect [[2,1,0,1]] as a result. Instead, I'm seeing [[2,1,0,1],[2,1,0,1]].

The program is supposed to accumulate distinct digit patterns of length m by adding a different digit to the list each time, returning back down when reaching n-1 and up when reaching 0. The apparent problem happens in the middle when the function is called recursively for both the up and down directions.

If I comment out line 11 like so:

else g n m (digitCount + 1) (lastDigit + 1) (hash',hashCount') (lastDigit:digits)
  -- g n m (digitCount + 1) (lastDigit - 1) (hash',hashCount') (lastDigit:digits)

I get the correct result []

As when commenting out line 11 and modifying line 10 to:

else g n m (digitCount + 1) (lastDigit - 1) (hash',hashCount') (lastDigit:digits)

Again, a correct result [[2,1,0,1]]

Why when calling g twice using the ++ operator, I'm getting two [2,1,0,1]'s instead of just one? In my thinking, each result in g should be distinct because in any recursive call, a different order of digits is (or should be) accumulating.

Thanks in advance.

import qualified Data.Map as M

g :: Int -> Int -> Int -> Int -> (M.Map Int Bool, Int) -> [Int] -> [[Int]]
g n m digitCount lastDigit (hash,hashCount) digits
  | digitCount == m = if test then [reverse digits] else []
  | otherwise       =
      if lastDigit == 0
         then g n m (digitCount + 1) (lastDigit + 1) (hash',hashCount') (lastDigit:digits)
         else if lastDigit == n - 1
                 then g n m (digitCount + 1) (lastDigit - 1) (hash',hashCount') (lastDigit:digits)
                 else g n m (digitCount + 1) (lastDigit + 1) (hash',hashCount') (lastDigit:digits)
                   ++ g n m (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)

解决方案

Why when calling g twice using the ++ operator, I'm getting two [2,1,0,1]'s instead of just one? In my thinking, each result in g should be distinct because in any recursive call, a different order of digits is (or should be) accumulating.

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

Also, (Map a ()) is a (Set a), and since you don't use the Bool value from the map, it is the same as ():

    import qualified Data.Set as S

    g :: Int -> Int -> Int -> Int -> (S.Set Int, Int) -> [Int] -> [[Int]]
    g n m digitCount lastDigit (hash,hashCount) digits
      | digitCount == m = if test then [reverse digits] else []
      | lastDigit < 0 || lastDigit == n  = []
      | otherwise       = g n m d' (lastDigit + 1) h' (lastDigit:digits)
                          ++ g n m d' (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)

这篇关于递归混淆在Haskell中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！