2

我必须定义一个无限的骑自行车的人

enumInts::Cyclist Integer

包含所有自然顺序的整数，零是当前元素。

我所做的是：

data Cyclist a=Elem (Cyclist a) a (Cyclist a) 

enumInts:: Cyclist Integer 
enumInts=Elem prev 0 next 
      where 
            prev=help2 enumInts 0 
            next=help1 enumInts 0 

-- Create positive part 
help1::Cyclist Integer -> Integer -> Cyclist Integer 
help1 prev n=present 
      where present=Elem prev (n+1) next 
                        where next=help1 present (n+1) 

-- Create negative part 
help2::Cyclist Integer -> Integer -> Cyclist Integer 
help2 next n=present 
      where present=Elem prev (n-1) next 
                        where prev=help2 present (n-1)

它正在编译自己。但我不确定它是否能正常工作......所以我想看看它的结果，例如。11个单位。它应该是：-5 -4 -3 -2 -1 0 1 2 3 4 5 值。有可能看到吗？（我知道它是无限的）但是例如。在斐波那契数列中，我们可以使用 'take 11 fibs' 它给了它们。这里选项'take n..'不起作用（嗯，或者它有效，但我不知道如何使用它）。我会很感激你的帮助..

4

5 回答 5

3

现在已经过了你的最后期限，我敢肯定，所以我很开心处理双无限整数：

允许有限部分

要制作一个 take 函数，我必须编辑您的类型，使其可以是有限的：

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

这不是我们想要的结构——它有三个零！

     0     
     |     
   -----   
  /     \  
  -1    1  
  |     |  
 ---    -- 
/   \  /  \
-2  0  0  2    -- oops! We've re-created zero for 1 and -1

最后每个数字都有两个0s和两个。如果我们更深入，那就更糟了

*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的 s 令人困惑。

制作符合您预期的数据类型。

我们真正需要的是一个当前元素，类似于向右延伸的列表，以及向左向后延伸的列表。编译器没有方向感，所以我们将对两者使用相同的结构，但请记住将左侧向后打印到右侧。

首先，我们需要一个绝对无限的列表：

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]
于 2012-11-24T18:45:16.297 回答
0

我认为这可以解决为：

我们的无限数据

myList = ([0] ++ ) $ conca­t $ [[x] ++  [-x] | x <- [1..]]

从此列表中获取特定数量的元素：

takeOnly n = sort $ take n myList
于 2011-05-30T08:53:59.863 回答
0

尽管它是内置的，但您可以将列表类型想象为定义为

data [a] = [] | a : [a]

take可以这样定义：

take 0 xs = []
take n (x:xs) = x:take (n-1) xs

您应该尝试查看如何take为您自己的类型调整定义。

于 2011-05-30T08:13:24.340 回答
0

这是我的解决方案：

enumInts :: Cyclist Integer
enumInts = Elem (goLeft enumInts) 0 (goRight enumInts)
    where
        goLeft this@(Elem left n _) = let left = Elem (goLeft left) (n-1) this in left
        goRight this@(Elem _ n right) = let right = Elem this (n+1) (goRight right) in right

你可以这样使用它：

label . forward . backward . forward . forward $ enumInts

在哪里：

label (Elem _ x _) = x
forward (Elem _ _ x) = x
backward (Elem x _ _) = x
于 2011-06-05T19:55:09.617 回答
0

当你想要这些数字时，为什么不直接使用

enumInts :: Integer -> [Integer]
enumInts n = [-(n`div`2)..(n`div`2)]
于 2011-05-30T07:52:20.020 回答