在這個函數中的習慣性哈斯克爾終止遞歸方式

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這樣的通用函數來很容易地解決這些問題。這是一個很高的學習曲線，但結果是值得的！