15

入力が無限に多くの値を取ることができる場合、リストを使用して非決定性をモデル化することは問題があります。例えば

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

これは戻り[(0,1),(0,2),(0,3),...]、最初の要素が ではないペアを表示することはありません0。

Cantor ペアリング関数を使用して、リストのリストを 1 つのリストに折りたたむことで、この問題を回避できます。たとえば、バインドのような演算子を定義して、出力をよりインテリジェントに並べ替えることができます。

(>>>=) :: [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

これをモナドとしてまとめると、すべての可能なペアを列挙できます

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)-私の直感では、この問題の適切な解決策は、アルゴリズムへの明示的な入力である可能性があるか、暗黙的に与えられる可能性がある「サイズ」の概念に従って出力を順序付けることです(この例では、入力の「サイズ」は入力リスト内の位置です)。入力を組み合わせる場合、組み合わせの「サイズ」は、入力のサイズの関数 (おそらく合計) にする必要があります。

私が見逃しているこの問題に対するエレガントな解決策はありますか?

4

4 に答える 4

7

TL;DR: 一度に 3 つのディメンションをフラット化するのではなく、一度に 2 つのディメンションをフラット化します。モナドでこれを整理することはできません>>=。バイナリではなく、ターナリなどです。

私はあなたが定義したと仮定します

(>>>=) :: [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完全性を疑っていますが、その必要はありません。同じトリックを実行していますが、3 つすべてを一度に行うのではなく、2 回実行しています。

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

2 番目のペアは単一のデータ ソースとして扱われるため、次の点に注意してください。

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)]

まったく同じパターンを使用していることがわかります。これは総和を保持するものではなく、3 番目の次元を平坦化する前に最初に 2 つの次元を平坦化することによって 3 次元になるため、そうすべきではありません。 .

悲しいことに、和を維持する方法で 3 次元を実行したい場合はcantor2、 、cantor3およびcantor4関数、場合によっては関数を記述するcantorN必要がありますが、本質的に のブラケットに基づいているモナド インターフェイスを破棄する必要があります。>>=したがって、一度に 2 つの次元の平坦化。

于 2013-12-20T21:06:25.447 に答える
4

omegaパッケージはまさにあなたが望むことを行い、すべての要素が最終的に訪問されることを保証します:

import Control.Applicative
import Control.Monad.Omega

main = print . take 200 . runOmega $
  (,,) <$> each [0..] <*> each [0..] <*> each [0..]

別のオプションは、LogicTを使用することです。これにより、(必要に応じて) 柔軟性が向上(>>-)し、すべての組み合わせが最終的に遭遇することを保証するなどの操作が行われます。

import Control.Applicative
import Control.Monad
import Control.Monad.Logic

-- | Convert a list into any MonadPlus.
each :: (MonadPlus m) => [a] -> m a
each = msum . map return

-- | A fair variant of '(<*>)` that ensures that both branches are explored.
(<@>) :: (MonadLogic m) => m (a -> b) -> m a -> m b
(<@>) f k = f >>- (\f' -> k >>- (\k' -> return $ f' k'))
infixl 4 <@>

main = print . observeMany 200 $
  (,,) <$> each [0..] <@> each [0..] <@> each [0..]
于 2013-12-21T14:16:21.307 に答える