P77 - List Monad 枚举随机游走路径

List monad
官方模块：Problems.P77　核心函数：randomWalkPaths

← P76 Either Monad | P78 Writer Monad 与 Collatz →

题目描述

从位置 0 出发，每一步可以移动 -1、0 或 1。返回长度为 $n$ 的所有选择所形成的位置路径，路径包含起点。

实现

方法一：list monad do 记法

 1randomWalkPaths :: Int -> [[Int]]
 2randomWalkPaths n
 3  | n < 0     = []
 4  | otherwise = map reverse (walk n)
 5  where
 6    walk 0 = [[0]]
 7    walk k = do
 8      reversedPath@(position:_) <- walk (k - 1)
 9      step <- [-1, 0, 1]
10      pure ((position + step) : reversedPath)

列表 Monad 把每次 step 的三个可能分支与已有路径做笛卡尔积。内部反向保存路径可用 (:) 常数时间扩展，最后统一 reverse。

方法二：先枚举步长，再求前缀和

1import Control.Monad (replicateM)
2
3randomWalkPaths :: Int -> [[Int]]
4randomWalkPaths n
5  | n < 0     = []
6  | otherwise = map (scanl (+) 0) (replicateM n [-1, 0, 1])

replicateM n choices 先生成所有长度为 $n$ 的步长序列，再用 scanl (+) 0 把步长转换成包含起点的位置序列。方法一直接扩展路径，方法二则把“选择”和“累计位置”分成两步。

方法对比

方法	中间表示
递归扩展	反向的位置路径
`replicateM` + `scanl`	步长序列，然后转为位置

测试

1>>> randomWalkPaths 1
2[[0,-1],[0,0],[0,1]]
3>>> length (randomWalkPaths 4)
481
5>>> all ((== 5) . length) (randomWalkPaths 4)
6True

$n$ 步共有 $3^n$ 条路径，输出规模本身就是指数级。

参考

← P76 Either Monad | P78 Writer Monad 与 Collatz →