haskell - 无限输入的非确定性

Question

如果输入可以采用无限多的值，则使用列表对不确定性建模是有问题的。例如

pairs = [ (a,b) | a <- [0..], b <- [0..] ]

这将返回 [(0,1),(0,2),(0,3),...]并且永远不要向您展示任何第一个元素不是 0 的对.

使用 Cantor pairing function将列表列表折叠成一个列表可以解决这个问题。例如，我们可以定义一个类似绑定(bind)的运算符，它通过以下方式更智能地对其输出进行排序

(>>>=) :: [a] -> (a -> [b]) -> [b]
as >>>= f = cantor (map f as)

cantor :: [[a]] -> [a]
cantor xs = go 1 xs
  where
    go _ [] = []
    go n xs = hs ++ go (n+1) ts
      where
        ys = filter (not.null) xs
        hs = take n $ map head ys
        ts = mapN n tail ys

mapN :: Int -> (a -> a) -> [a] -> [a]
mapN _ _ []   = []
mapN n f xs@(h:t)
  | n <= 0    = xs
  | otherwise = f h : mapN (n-1) f t

如果我们现在把它包装成一个单子(monad)，我们可以枚举所有可能的对

newtype Select a = Select { runSelect :: [a] }

instance Monad Select where
    return a = Select [a]
    Select as >>= f = Select $ as >>>= (runSelect . f)

pairs = runSelect $ do
    a <- Select [0..]
    b <- Select [0..]
    return (a,b)

这导致

>> take 15 pairs
[(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0),(0,4),(1,3),(2,2),(3,1),(4,0)]

这是一个更理想的结果。但是，如果我们要改为要求三元组，则输出的排序就不是那么“好”了，而且我什至不清楚所有输出最终都包括在内——

>> take 15 triples
[(0,0,0),(0,0,1),(1,0,0),(0,1,0),(1,0,1),(2,0,0),(0,0,2),(1,1,0),(2,0,1),(3,0,0),(0,1,1),(1,0,2),(2,1,0),(3,0,1),(4,0,0)]

请注意 (2,0,1)出现在 (0,1,1) 之前在排序中——我的直觉说，这个问题的一个好的解决方案将根据“大小”的一些概念对输出进行排序，这可能是算法的显式输入，也可能是隐式给出的(如本例中，其中输入的“大小”是它在输入列表中的位置)。组合输入时，组合的“大小”应该是输入大小的某个函数(可能是总和)。

我缺少这个问题的优雅解决方案吗？

Answer 1

TL;DR:它一次展平两个维度，而不是一次展平三个。你不能在 monad 中整理它，因为 >>=是二元的，不是三元的等。

我假设你定义了

(>>>=) :: [a] -> (a -> [b]) -> [b]
as >>>= f = cantor $ map f as

交错列表列表。

你喜欢这样，因为它是对角线的:

sums = runSelect $ do
    a <- Select [0..]
    b <- Select [0..]
    return (a+b)

给

ghci> take 36 sums
[0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7]

所以它令人愉快地保持“尺寸”的顺序，但 triples 的模式似乎被打破了，你怀疑完整性，但你不需要。它做同样的把戏，但两次，而不是一次全部三个:

triplePairs = runSelect $ do
    a <- Select [0..]
    b <- Select [0..]
    c <- Select [0..]
    return $ (a,(b,c))

第二对被视为单一数据源，因此请注意:

ghci> map fst $ take 36 pairs
[0,0,1,0,1,2,0,1,2,3,0,1,2,3,4,0,1,2,3,4,5,0,1,2,3,4,5,6,0,1,2,3,4,5,6,7]
ghci> map fst $ take 36 triplePairs
[0,0,1,0,1,2,0,1,2,3,0,1,2,3,4,0,1,2,3,4,5,0,1,2,3,4,5,6,0,1,2,3,4,5,6,7]

和(添加一些空格/换行符以使模式清晰):

ghci> map snd $ take 36 pairs
[0, 1,0, 2,1,0, 3,2,1,0, 4,3,2,1,0, 5,4,3,2,1,0, 6,5,4,3,2,1,0, 7,6,5,4,3,2,1,0]
ghci> map snd $ take 36 triplePairs
[(0,0),  (0,1),(0,0),  (1,0),(0,1),(0,0),  (0,2),(1,0),(0,1),(0,0), 
 (1,1),(0,2),(1,0),(0,1),(0,0), 
 (2,0),(1,1),(0,2),(1,0),(0,1),(0,0), 
 (0,3),(2,0),(1,1),(0,2),(1,0),(0,1),(0,0), 
 (1,2),(0,3),(2,0),(1,1),(0,2),(1,0),(0,1),(0,0)]

所以你可以看到它使用完全相同的模式。这不会保留总和，也不应该因为我们通过在展平第三个维度之前先展平两个维度来达到三个维度。模式是模糊的，但它可以保证到达列表的末尾.

遗憾的是，如果你想以求和的方式做三个维度，你必须写 cantor2 , cantor3和 cantor4函数，可能是 cantorN函数，但是你必须放弃单子(monad)接口(interface)，它本质上是基于 >>= 的括号。 ，因此一次两次展平尺寸。