无限输入的非确定性

Question

如果输入可以采用无限多的值,则使用列表来模拟非确定性是有问题的.例如

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

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

使用Cantor配对功能将列表列表折叠到单个列表中可以解决此问题.例如,我们可以定义一个类似绑定的运算符,它可以更智能地对其输出进行排序

(>>>=) :: [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功能,但你必须沟单子接口,它本质上是基于对包围>>=,因此一次两个扁平的尺寸.