2

次のデータ型定義があるとします。

data FormTree = Empty | Node FormTree FormTree deriving Show

ノードの量などの長さでソートされたすべての可能なツリーを含む無限リストを生成する関数を書きたいと思います。

次のコードは、必要なことをほぼ実行しますが、毎回追加のノードを挿入して右側のツリーを下るだけですが、両側を交互に切り替える必要があります。

allPossibleTrees :: [FormTree]
allPossibleTrees = Empty : [Node x y | x <- recursive, y <- recursive]
    where recursive = allPossibleTrees

実行中

take 5 allPossibleTrees

与えます：

[Empty,Node Empty Empty,Node Empty (Node Empty Empty),Node Empty (Node Empty (Nodes Empty Empty)),Node Empty (Node Empty (Node Empty (Node Empty Empty)))]

しかし、それは次のようなものでなければなりません:

[Empty,Node Empty Empty,Node (Node Empty Empty) Empty,Node Empty (Node Empty Empty),Node (Node Empty Empty) (Node Empty Empty)]
4

4 に答える 4

4

リスト内包表記

[ (x,y) | x<-[1..] , y<-[1..] ]

可能なすべてのs のすべてx=1のペアを検討して構築することから始めます。次に、およびすべてのペアが続きます。等々。(1,y)yx=2(2,y)

ただし、無限に多くの(1,y)ペアがあるためx=2、無限の時間が経過した後にのみ考慮されます。つまり、まったく考慮されません。

あなたのコードは同じ問題に苦しんでいます。

考えられる解決策を確認するには、オメガモナドを利用してすべてのケースで公平なスケジューリングを実現するこの関連する質問を参照できます。

于 2015-01-22T23:46:27.967 に答える
1

control-monad-omegaライブラリは、元のコードでトリックを行うようです:

{-# LANGUAGE MonadComprehensions #-}

import Control.Monad.Omega

data Empty = Empty | Node Empty Empty deriving Show

allPossibleTrees :: [Empty]
allPossibleTrees = Empty : 
    runOmega [Node x y | x <- each allPossibleTrees, y <- each allPossibleTrees]

最初の 10 本の木は私には良さそうです。

*Main> mapM_ print $ take 10 allPossibleTrees 
Empty
Node Empty Empty
Node Empty (Node Empty Empty)
Node (Node Empty Empty) Empty
Node Empty (Node Empty (Node Empty Empty))
Node (Node Empty Empty) (Node Empty Empty)
Node (Node Empty (Node Empty Empty)) Empty
Node Empty (Node (Node Empty Empty) Empty)
Node (Node Empty Empty) (Node Empty (Node Empty Empty))
Node (Node Empty (Node Empty Empty)) (Node Empty Empty)
于 2015-01-24T11:15:41.963 に答える