P78 - 用 Writer Monad 统计 Collatz 步数

Collatz conjecture with Writer
官方模块：Problems.P78　核心函数：collatz

← P77 List Monad | P79 Monad Transformer 后缀求值 →

题目描述

正整数为奇数时变为 $3n+1$ ，为偶数时变为 $n/2$ 。用 Writer 的累积日志统计到达 1 所需的步数。

实现

方法一：递归过程中写日志

 1import Control.Monad.Writer (Writer, execWriter, tell)
 2import Data.Monoid (Sum(..))
 3
 4collatz :: Integral a => a -> a
 5collatz n
 6  | n < 1     = error "collatz: positive input required"
 7  | otherwise = getSum (execWriter (walk n))
 8
 9walk :: Integral a => a -> Writer (Sum a) ()
10walk 1 = pure ()
11walk n = do
12  tell (Sum 1)
13  walk (if odd n then 3*n + 1 else n `div` 2)

Sum a 的 Monoid 运算是加法，tell (Sum 1) 每执行一次就把计数增加 1；execWriter 丢弃普通返回值，只取日志。

方法二：先生成序列，再统一记录

 1collatzViaSequence :: Integral a => a -> a
 2collatzViaSequence n
 3  | n < 1     = error "collatz: positive input required"
 4  | otherwise = getSum . execWriter $
 5      mapM_ (const (tell (Sum 1))) (tail (collatzSequence n))
 6
 7collatzSequence :: Integral a => a -> [a]
 8collatzSequence 1 = [1]
 9collatzSequence n = n : collatzSequence next
10  where
11    next = if odd n then 3 * n + 1 else n `div` 2

这个版本先构造从输入到 1 的完整序列。除去首项后，每个元素对应一次状态转移，再用 Writer 为每项记录 Sum 1。它占用更多内存，但把数列生成和效果累积分离开。

方法对比

方法	过程
递归写日志	计算下一项时立即 `tell`
序列后处理	先生成惰性序列，再用 Writer 统计转移

测试

1>>> collatz 1
20
3>>> collatz 6
48
5>>> collatz 27
6111
7>>> collatzViaSequence 27
8111

算法是否对所有正整数终止正是 Collatz 猜想的内容；代码只能对实际输入执行，不能证明全局终止性。

参考

← P77 List Monad | P79 Monad Transformer 后缀求值 →