haskell - 为什么 `fmap` 需要在 `succ` 上调用 `Maybe Integer` ？

Question

我是 Haskell 的新手，正在研究 Collat​​z 猜想问题。所需的输出是从给定整数到 1 所需的步数。这是我第一次不得不使用 Maybe 类型，这可能会造成我的困惑。

我有这个可行的解决方案基于我发现的针对同一问题的另一个解决方案:

collatz :: Integer -> Maybe Integer
collatz n
    | n <= 0 = Nothing
    | n == 1 = Just 0
    | even n = fmap succ . collatz $ n `div` 2
    | otherwise = fmap succ . collatz $ 3 * n + 1

我不清楚为什么在这种情况下需要使用 fmap succ。根据我目前的理解，我希望能够在递归调用 collat​​z 的输出上调用 succ 以增加它；但是，这会引发错误:

> No instance for (Enum (Maybe Integer))
        arising from a use of `succ'

看起来该错误与在 Maybe Integer 类型而不是 Integer 上调用 succ 有关。错误是因为 Maybe Integer 在 Haskell 中不被认为是可枚举的吗？如果是这样，为什么调用 fmap succ 可以解决这个问题？

Answer 1

如果您刚开始学习 Haskell，使用 . 和 $ 会不必要地为您带来额外的认知负担。你所拥有的更简单的写成

collatz :: Integer -> Maybe Integer
collatz n
    | n <= 0    = Nothing
    | n == 1    = Just 0
    | even n    = fmap succ (collatz (n `div` 2))
    | otherwise = fmap succ (collatz (3 * n + 1))

现在，succ 是什么？如果我们看一下它的类型，

> :t succ
succ :: Enum a => a -> a

主要需要注意的是输入和输出类型是相同的。它也是 Enum 类型类的一个实例，也就是说这个类型实现了它特定版本的 succ 函数(这样有点循环) .

因为我们正在处理 Integer，它们确实将自己的 succ 版本实现为

succ :: Integer -> Integer
succ i = i + 1

一切都很好，得到了照顾。

除了 collat​​z::Integer -> Maybe Integer 接受一个 Integer 并返回一个 Maybe Integer:

-- pseudocode
Maybe Integer = Nothing
              | Just      Integer
             -- ^ tags    ^ types of contained data

所以我们需要将 succ 应用到 contained Integer。这就是 fmap 的工作:

-- pseudocode
> :t fmap
fmap :: Functor f => (a -> b) -> f     a -> f     b
> :t fmap @ Maybe
fmap ::              (a -> b) -> Maybe a -> Maybe b
> :t fmap @ Maybe succ @ Integer
fmap ::                    Maybe Integer -> Maybe Integer

这是一个由一类类型定义的通用函数，每个类型都定义了它的专用版本。 Maybe 确实如此:

-- pseudocode:
fmap f Nothing  = Nothing
fmap f (Just i) = Just (f i)
                --      ^^ f applied on the "inside"
                --      ^^ when there is something in there