了解递归的Haskell/GHCI行为

Question

我试图通过以下功能理解我所看到的内容.不确定我的理解是否不正确,或者这是否是特定于Haskell的GHC实现的行为.

countNumLastChar :: Eq a => [a] -> (a, Int)
countNumLastChar [x]      = (x, 1)
countNumLastChar (x:xs)  = if x == fst y
                            then (fst y, (snd y) + 1)
                            else y
                            where y = countNumLastChar xs

我正在看到一些我无法用这段代码解释的东西.

*Main> countNumLastChar "aba"
('a',2)
*Main> countNumLastChar "abql;kejrqlwkjer;lqwkejr;lwjerca"
('a',2)
*Main> countNumLastChar "abql;kejrqlwkjer;lqwkejr;lwjercap"
('p',1)
*Main> countNumLastChar "abql;kejrqlwkjer;lqwkejr;lwjerca;"
(';',4)

例如:使用GHCI跟踪下面的运行,我看到当我们使用尚未重复的元素到达单例列表时,我们不会递回每一步.

*Main> countNumLastChar "aabc"
('c',1)
[maxOccurCharInStr.hs:(3,28)-(5,34)] *Main> :step
Stopped at maxOccurCharInStr.hs:3:31-40
_result :: Bool = _
x :: Char = 'b'
y :: (Char, Int) = _
[maxOccurCharInStr.hs:3:31-40] *Main> :list
2  countNumLastChar [x]      = (x, 1)
3  countNumLastChar (x:xs)  = if x == fst y
4                              then (fst y, (snd y) + 1)
[maxOccurCharInStr.hs:3:31-40] *Main> :step
Stopped at maxOccurCharInStr.hs:3:36-40
_result :: a = _
y :: (a, Int) = _
[maxOccurCharInStr.hs:3:36-40] *Main> :step
Stopped at maxOccurCharInStr.hs:6:39-57
_result :: (Char, Int) = _
xs :: [Char] = 'c' : _
[maxOccurCharInStr.hs:6:39-57] *Main> :list
5                              else y
6                              where y = countNumLastChar xs
7  
[maxOccurCharInStr.hs:6:39-57] *Main> :step
Stopped at maxOccurCharInStr.hs:(2,1)-(6,57)
_result :: (a, Int) = _
[maxOccurCharInStr.hs:(2,1)-(6,57)] *Main> :list
1  countNumLastChar :: Eq a => [a] -> (a, Int)
2  countNumLastChar [x]      = (x, 1)
3  countNumLastChar (x:xs)  = if x == fst y
4                              then (fst y, (snd y) + 1)
5                              else y
6                              where y = countNumLastChar xs
7  
[maxOccurCharInStr.hs:(2,1)-(6,57)] *Main> :step
Stopped at maxOccurCharInStr.hs:2:29-34
_result :: (Char, Int) = _
x :: Char = 'c'
[maxOccurCharInStr.hs:2:29-34] *Main> :list
1  countNumLastChar :: Eq a => [a] -> (a, Int)
2  countNumLastChar [x]      = (x, 1)
3  countNumLastChar (x:xs)  = if x == fst y
[maxOccurCharInStr.hs:2:29-34] *Main> :step
('c',1)
*Main> 

我期待最后一个:step会让我回到else y定义中的情况,但我发现结果立即返回.但是当最后一个字母出现之前我们会回复并做(fst y, (snd y) + 1)部分...有人可以告诉你发生了什么吗？是我的理解不正确或GHCI优化的东西.如果它正在优化,它怎么知道它必须直接返回结果？任何对此的提及都会有很大帮助.

Answer 1

您期望的递归（即 的求值else y）是 Haskell 的惰性求值中不需要的程序期望。

• ywhere y = countNumLastChar xs当需要计算 时，已经在语句中计算过if，因此不需要再次计算。（else y没有出现在跟踪中，因为没有什么新的东西可以评估）
• then (fst y, (snd y) + 1)当函数到达单例情况时尚未对其进行评估，因此您确实会看到它在返回递归堆栈的过程中进行评估。

如果您要将 else 情况更改为在单例情况之后才能评估的内容，则它将在返回递归调用的过程中进行评估。