在这个函数中的习惯性哈斯克尔终止递归方式

Question

停止这个函数递归的更方便的方法是什么？目前我使用嵌套的if/else，如果下一个组合“溢出”，则返回一个空列表。

nextcomb [] []  = [] 
nextcomb lst maxes | length lst == length maxes = 
let lastel = last lst 
in if lastel < last maxes 
    then (init lst) ++ [lastel+1] 
    else let higherbit = (nextcomb (init lst) (init maxes)) 
     in if higherbit == [] 
      then [] 
      else higherbit ++ [1] 
nextcomb lst maxes | otherwise = [] 

为了澄清，它的作用是它需要像[1,1,1,1]和增量它喜欢数字的列表：

[1,1,1,1] - > [1,1,1,2]

...

[1,1,1,9] - > [1,1,2,1]

...

[1,1,9,9] - > [1,2,1,1]

等

但是，第二个参数是一个列表，指示每列的最大值。因此，如果是马克塞斯[2,3]，和初始列表是[1,1]，则进展woudld是：

[1,1] - >并[1,2]

[1 ，2] - > [1,3]

[1,3] - >并[2,1]

[2,1] - > [2,2]

[2,2 ] - > [2,3]

[2,3] - > []

---

编辑：“小端”版本所推荐的chepner

nextcomb' [] [] = [] 
nextcomb' lst maxes | length lst /= length maxes = [] 
nextcomb' lst maxes = 
    let firstel = head lst 
    in if firstel < head maxes 
     then (firstel+1) : (tail lst) 
     else let higherbit = (nextcomb' (tail lst) (tail maxes)) 
      in if higherbit == [] 
       then [] 
       else 1 : higherbit 

Answer 1

你if表达仅仅是隐藏真正的基本情况，这是如果要么参数为空，则返回空列表。

nextcomb [] [] = [] 
nextcomb lst maxes | length lst != length maxes = [] 
nextcomb lst maxes = let lastel = last lst 
        in if lastel < last maxes 
         then (init lst) ++ [lastel+1] 
         else let higherbit = (nextcomb (init lst) (init maxes)) 
          in if higherbit == [] 
           then [] 
           else higherbit ++ [1] 

我可能会重写这样的逻辑。 （请注意，我从一个Haskell专家很远，而且往往回答这些问题，作为一个练习自己:)

-- Reversing the arguments and the ultimate return value 
-- lets you work with the head of each list, rather than the last 
-- element 
nextcomb lst maxes = reverse $ nextcomb' (reverse lst) (reverse maxes) 
-- The real work. The base case is two empty lists 
nextcomb' [] [] = [] 
-- If one list runs out before the other, it's an error. I think 
-- it's faster to check if one argument is empty when the other is not 
-- than to check the length of each at each level of recursion. 
nextcomb' [] _ = error "maxes too long" 
nextcomb' _ [] = error "maxes too short" 
-- Otherwise, it's just a matter of handling the least-significant 
-- bit correctly. Either abort, increment, or reset and recurse 
nextcomb' (x:xs) (m:ms) | x > m = error "digit too large" 
         | x < m = (x+1):xs -- just increment 
         | otherwise = 0:(nextcomb' xs ms) -- reset and recurse 

（实际上，注意，如果你没有在最后递归nextcomb' [] _不会触发你可能会认为太长的maxes不是什么大问题，我会留下这个不确定的，因为下一部分正确处理它。）

或者，你可以验证长度匹配的初始调用;那么你可以假设两者将同时变空。

nextcomb lst maxes | length lst == length maxes = reverse $ nextcomb' (reverse lst) (reverse maxes) 
        | otherwise = error "length mixmatch" 

nextcomb' [] [] = [] 
nextcomb' (x:xs) (m:ms) | x > m = error "digit too large" 
         | x < m = (x+1):xs 
         | otherwise = 0:(nextcomb' xs ms) 

---

下面是使用Either报告错误的例子。除了说输入检查和运行外，我不会担保设计。它与以前的代码没有太大差别;它只是使用<$>来解除reverse和(0:)以使用Either String [a]类型的参数而不是[a]类型的参数。

import Control.Applicative 
nextcombE lst maxes = reverse <$> nextcombE' (reverse lst) (reverse maxes) 

nextcombE' [] [] = Right [] 
nextcombE' [] _ = Left "maxes too long" 
nextcombE' _ [] = Left "maxes too short" 
nextcombE' (x:xs) (m:ms) | x > m = Left "digit too large" 
         | x < m = Right ((x+1):xs) 
         | otherwise = (0:) <$> (nextcombE' xs ms) 

Answer 2

请检查下一个实现对您有用，因为更多的“haskellish”的方式（至少对我来说），使用内置的递归函数来达到同样的目标

nextcomb [] [] = [] 
nextcomb lst maxes 
    | length lst /= length maxes = [] 
    | lst == maxes = [] 
    | otherwise = fst $ foldr f ([],True) $ zip lst maxes 
    where 
    f (l,m) (acc, mustGrow) 
     | mustGrow && l < m = (l + 1:acc, False) 
     | mustGrow = (1:acc, True) 
     | otherwise = (l:acc, False) 

（编者）如果需要捕获错误，那么可以试试这个：

nextcomb [] _ = Left "Initial is empty" 
nextcomb _ [] = Left "Maximus size are empty" 
nextcomb lst maxes 
    | length lst /= length maxes = Left "List must be same length" 
    | lst == maxes = Left "Initial already reach the limit given by Maximus" 
    | otherwise = Right $ fst $ foldr f ([],True) $ zip lst maxes 
    where 
    f (l,m) (acc, mustGrow) 
     | mustGrow && l < m = (l + 1:acc, False) 
     | mustGrow = (1:acc, True) 
     | otherwise = (l:acc, False) 

Answer 3

你应该让非法状态不可表示

因此，不是使用两个列表，而是使用元组列表。例如，每个元组中的第一个值可能是最大值，第二个值是实际值。

这也大大简化了逻辑，因为错误“最长时间太长”和“最长时间太短”不能发生。

Answer 4

让我们画一个图！我会做出与最初的问题略有不同的假设：

1. 像chepner建议的小端代表;
2. 取而代之的是包容性最大值，我打算用独家基地来使事情更类似于“随身携带”。
3. 我打算使用[0, base)范围内的数字。

这里的图：

digits = [d0, d1, ..., dn] 
bases = [b0, b1, ..., bn] 
-------------------------- 
result = [r0, r1, ..., rn] 

现在，我们可以问：对于结果的每一位ri，什么是它的价值取决于？好了，这些东西：

1. 的di
2. 价值bi
3. 无论以前r产生进位值

因此，我们可以这样写一个函数：

import Control.Monad.State -- gonna use this a bit later 

type Base = Int 
type Digit = Int 
type Carry = Bool 

-- | Increment a single digit, given all the contextual information. 
singleDigit' :: Base -> Digit -> Carry -> (Digit, Carry) 
singleDigit' base digit carry = (digit', carry') 
    where sum = digit + if carry then 1 else 0 
      digit' = if sum < base then sum else sum - base 
      carry' = base <= sum 

请注意，我小心确保singleDigit'函数的类型以Carry -> (Digit, Carry)结尾。这是因为符合state -> (result, state)图案是典型的状态单子：

increment :: [Base] -> [Digit] -> [Digit] 
increment bases digits = evalState (sequence steps) True 
    where steps :: [State Carry Digit] 
      steps = zipWith singleDigit bases digits 

我们在这里所做的是：：

-- | Wrap the `singleDigit'` function into the state monad. 
singleDigit :: Base -> Digit -> State Carry Digit 
singleDigit base digit = state (singleDigit' base digit) 

与我们可以写出下面的函数

现在

1. 使用zipWith在相应的元素上“缝合”基数和数字列表。该列表的元素对应于计算的各个steps。
2. 使用sequence :: [State Carry Digit] -> State Carry [Digit]将所有单个步骤链接成一个大步骤，通过中间状态Carry。
3. 喂养True作为初始的Carry输入到该大步骤链（导致链增加）。

实例调用：

>>> take 20 (iterate (increment [3,4,5,10]) [0,0,0,0]) 
[[0,0,0,0],[1,0,0,0],[2,0,0,0] 
,[0,1,0,0],[1,1,0,0],[2,1,0,0] 
,[0,2,0,0],[1,2,0,0],[2,2,0,0] 
,[0,3,0,0],[1,3,0,0],[2,3,0,0] 
,[0,0,1,0],[1,0,1,0],[2,0,1,0] 
,[0,1,1,0],[1,1,1,0],[2,1,1,0] 
,[0,2,1,0],[1,2,1,0] 
] 

的教训我强调：

1. 歇问题成小块。不要试图在一个功能上解决太多问题！在这种情况下，诀窍是将单个数字的解决方案分解为它自己的功能。
2. 对于问题：在问题的每个步骤需要哪些信息需要仔细考虑数据流？在这种情况下，该图帮助理解了这一点，这导致了singleDigit'函数。
3. 函数式编程的一个重要思想是将计算的“形状”与其“内容”分开。在这种情况下，“内容”是singleDigit操作，而计算的“形状” - 如何将各个步骤组合为一个大的解决方案 - 由State monad和sequence操作提供。
4. 我没有写一个单一的递归函数;相反，我充分利用了库函数，如zipWith，sequence,take和iterate。你需要一个更加习惯的Haskell解决方案，很好，在这里：复杂的递归函数定义与使用封装常用递归模式的库函数不同。
5. 这有希望会鼓励你更多地学习单子。如果用State这样的标准monad之一来表达它们，那么可以使用像sequence这样的通用函数来很容易地解决这些问题。这是一个很高的学习曲线，但结果是值得的！