締め切りを過ぎてしまったので、二重無限整数を扱うのは楽しかったです。
有限部分の許可
テイク関数を作成するには、有限になるように型を編集する必要があります。
data Cyclist a=Elem (Cyclist a) a (Cyclist a) | Empty
deriving Show
takeToDepth :: Int -> Cyclist a -> Cyclist a
takeToDepth 0 _ = Empty
takeToDepth n (Elem c1 a c2)
| n >0 = Elem (takeToDepth (n-1) c1) a (takeToDepth (n-1) c2)
| otherwise = Empty
takeToDepth n Empty = Empty
しかし、データ型に誤りがあることがわかります。
*Main> takeToDepth 1 enumInts
Elem Empty 0 Empty
0 -- I've drawn the tree
と
*Main> takeToDepth 2 enumInts
Elem (Elem Empty (-1) Empty) 0 (Elem Empty 1 Empty)
0
| -- looks OK
--- -- see the end of the answer for how I pretty printed
/ \
-1 1
これまでのところ問題ないように見えますが、次のようになります。
*Main> takeToDepth 3 enumInts
Elem (Elem (Elem Empty (-2) Empty) (-1) (Elem Empty 0 Empty))
0 (Elem (Elem Empty 0 Empty) 1 (Elem Empty 2 Empty))
これは私たちが望む構造ではありません - ゼロが 3 つ含まれています!
0
|
-----
/ \
-1 1
| |
--- --
/ \ / \
-2 0 0 2 -- oops! We've re-created zero for 1 and -1
最後に 2つ0の s とすべての数字の 2 つがあります。深入りしたらもっとひどい
*Main> takeToDepth 4 enumInts
Elem (Elem (Elem (Elem Empty (-3) Empty) (-2) (Elem Empty (-1) Empty)) (-1)
(Elem (Elem Empty (-1) Empty) 0 (Elem Empty 1 Empty))) 0
(Elem (Elem (Elem Empty (-1) Empty) 0 (Elem Empty 1 Empty)) 1
(Elem (Elem Empty 1 Empty) 2 (Elem Empty 3 Empty)))
0
|
--------------------------
/ \
-1 1
| |
------------- -----------
/ \ / \
-2 0 0 2
| | | |
------- ----- ----- -----
/ \ / \ / \ / \
-3 -1 -1 1 -1 1 1 3
| | | | | | | |
--- --- --- -- --- -- -- --
/ \ / \ / \ / \ / \ / \ / \ / \
-4 -2 -2 0 -2 0 0 2 -2 0 0 2 0 2 2 4
真ん中にそんなものは必要ありません。私たちが望むのはもっと似ています
this = Elem (Elem (Elem (Elem Empty (-3) Empty) (-2) Empty) (-1) Empty)
0 (Elem Empty 1 (Elem Empty 2 (Elem Empty 3 Empty)))
0
|
---
/ \
-1 1
| |
-2 2
| |
-3 3
それはいいのですが、 が多すぎてEmpty混乱します。
意図したとおりのデータ型を作成します。
本当に必要なのは現在の要素で、右に伸びるリストのようなものと、左に後ろに伸びるリストのようなものです。コンパイラには方向感覚がないので、両方に同じ構造を使用しますが、左側を逆向きに右側に出力することを忘れないでください。
まず、確実に無限のリストが必要です。
data InfiniteList a = IL a (InfiniteList a) deriving Show
tailIL (IL _ therest) = therest
headIL (IL a _ ) = a
fromList [] = error "fromList: finite list supplied"
fromList (x:xs) = IL x (fromList xs)
toList (IL a therest) = a:toList therest
これで、両方向に無限にすることができます。
data DoublyInfiniteList a = DIL {left :: InfiniteList a,
here :: a,
right :: InfiniteList a}
deriving Show
enumIntsDIL = DIL {left = fromList [-1,-2..], here = 0, right = fromList [1..]}
次のようになります。
0
|
---
/ \
-1 1
| |
-2 2
| |
-3 3
| |
-4 4
9つだけではなく、無限に多くの要素があるだけです。
移動手段を作りましょう。reverseこれは、toListとを使用してより効率的にすることができますfromListが、このようにして、その部分をどのようにいじることができるかを確認できます。
go :: Int -> DoublyInfiniteList a -> DoublyInfiniteList a
go 0 dil = dil
go n dil | n < 0 = go (n+1) DIL {left = tailIL . left $ dil,
here = headIL . left $ dil,
right = IL (here dil) (right dil)}
go n dil | n > 0 = go (n-1) DIL {left = IL (here dil) (left dil),
here = headIL . right $ dil,
right = tailIL . right $ dil}
有限になりたいときはいつでも、別のデータ型に変換できるようになりました。
data LeftRightList a = LRL {left'::[a],here'::a,right'::[a]} -- deriving Show
toLRL :: Int -> DoublyInfiniteList a -> LeftRightList a
toLRL n dil = LRL {left' = take n . toList . left $ dil,
here' = here dil,
right' = take n . toList . right $ dil}
どちらが与える
*Main> toLRL 10 enumIntsDIL
LRL {left' = [-1,-2,-3,-4,-5,-6,-7,-8,-9,-10], here' = 0, right' = [1,2,3,4,5,6,7,8,9,10]}
しかし、おそらくそれを印刷したいので、あなたが意味するように見えます:
import Data.List -- (Put this import at the top of the file, not here.)
instance Show a => Show (LeftRightList a) where
show lrl = (show'.reverse.left' $ lrl) -- doesn't work for infinite ones!
++ ", " ++ show (here' lrl) ++ " ,"
++ (show' $ right' lrl) where
show' = concat.intersperse "," . map show
どちらが与える
*Main> toLRL 10 enumIntsDIL
-10,-9,-8,-7,-6,-5,-4,-3,-2,-1, 0 ,1,2,3,4,5,6,7,8,9,10
*Main> toLRL 10 $ go 7 enumIntsDIL
-3,-2,-1,0,1,2,3,4,5,6, 7 ,8,9,10,11,12,13,14,15,16,17
もちろん、リストに変換して表示することもできますが、現在の場所を示す機能は失われてしまいます。
付録: ツリーをきれいに印刷する方法
import Data.Tree
import Data.Tree.Pretty
いくつかの異なる種類のツリーなどが横たわっているので、それぞれをツリーに変換するクラスを自分で作成しました。
class TreeLike t where
toTree :: t a -> Tree a
treeTake :: Int -> Tree a -> Tree a
treeTake 1 (Node a _) = Node a []
treeTake n (Node a ts) | n > 1 = Node a (map (treeTake (n-1)) ts)
| otherwise = error "treeTake: attemt to take non-positive number of elements"
see :: (TreeLike t,Show a) => Int -> t a -> IO ()
see n = putStrLn.drawVerticalTree.fmap show.treeTake n.toTree
次のように使用します。
*Main> see 5 $ go (-2) enumIntsDIL
-2
|
---
/ \
-3 -1
| |
-4 0
| |
-5 1
| |
-6 2
まずあなたのサイクリスト:
instance TreeLike Cyclist where
toTree Empty = error "toTree: error - Empty"
toTree (Elem Empty a Empty) = Node a []
toTree (Elem Empty a c2) = Node a [toTree c2]
toTree (Elem c1 a Empty) = Node a [toTree c1]
toTree (Elem c1 a c2) = Node a [toTree c1,toTree c2]
次は二重無限リストです。
instance TreeLike InfiniteList where
toTree (IL a therest) = Node a [toTree therest]
instance TreeLike DoublyInfiniteList where
toTree dil = Node (here dil) [toTree $ left dil,toTree $ right dil]
そして、左右のリスト:
instance TreeLike [] where
toTree [] = error "toTree: can't make a tree out of an empty list"
toTree [x] = Node x []
toTree (x:ys) = Node x [toTree ys]
instance TreeLike LeftRightList where
toTree lrl = Node (here' lrl) [toTree $ left' lrl,toTree $ right' lrl]