当前位置： 文江博客话题详情

取无限结构的有限部分

发布于 2024-11-10 13:43:59 字数 949 浏览 5 评论 0原文

我必须定义一个无限循环者，

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 值。 可以看到吗？ （我知道它是无限的）但是例如。在斐波那契数列中，我们可以使用“取 11 个斐波那契数列”，它给出了它们。这里的选项“take n..”不起作用（嗯或者它起作用，但我不知道如何使用它）。 我会很感激你的帮助..

原文

I have to define an infinite cyclist

enumInts::Cyclist Integer

containing all integers in the natural order with zero being the current element.

What I did is:

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)

It is compiling itself. But I'm not sure if it works as it should... so I'd like to see its result for for eg. 11 units. It should be :-5 -4 -3 -2 -1 0 1 2 3 4 5 values.
Is it possible to see it? (I know its an infinite) but for eg. in fibonacci sequence we could use 'take 11 fibs' and it gave them. Here option 'take n..' doesn't work (hmm or it works but i dont know how to use it).
I'd be grateful for your help..

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（5）

油饼 2024-11-17 13:43:59

我确信现在已经超过了你的截止日期，所以我很高兴处理双无限整数：

允许有限部分

要制作一个 take 函数，我必须编辑你的类型，以便它可以< /em> 是有限的：

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

最后有两个0，每个数字都有两个。如果我们更深入，情况会更糟，

*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

That's good，但是有太多 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]

It's way past your deadline now, I'm sure, so I had fun dealing with the doubly-infinite Integers:

Allowing a finite part

To make a take function, I'll have to edit your type so that it can be finite:

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

But now we can see a mistake in your data type:

*Main> takeToDepth 1 enumInts
Elem Empty 0 Empty
0 -- I've drawn the tree

and

*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

It's looking OK so far, but:

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

That's not the structure we want - it has three zeros in it!

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

There are two 0s and two of every number in the end. It's even worse if we go deeper

*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

We don't need all that stuff in the middle. What we want is more like

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

That's good, but there are so many Emptys it's confusing.

Making a data type that does what you intend.

What we really need is a current element, somthing like a list stretching out to the right, and something like a list stretching out backwards to the left. The compiler doesn't have a sense of direction, so we'll use the same structure for both but remember to print the left hand side backwards on to the right hand side.

First we need a definitely-infinite list:

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

Now we can make it infinite in both directions:

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..]}

Which looks like this:

  0  
  |  
 --- 
/   \
-1  1
|   |
-2  2
|   |
-3  3
|   |
-4  4

only with infinitely many elements, not just 9.

Let's make a way of moving about. This could be made more efficient with use of reverse, toList and fromList, but this way you get to see how you can mess with the parts of it:

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}

We can now convert to another datatype every time we want to be finite.

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}

Which gives

*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]}

but you probably want to print that so it looks like what you mean:

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

Which gives

*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

Of course we could have just converted to a list and shown that, but we'd have lost the ability to indicate where we were.

Appendix: How I pretty-printed the trees

import Data.Tree
import Data.Tree.Pretty

There are a few different types of trees etc lying about so I gave myself a class to convert them each to Tree:

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

Which we use like this:

*Main> see 5 $ go (-2) enumIntsDIL
  -2  
  |   
 ---  
/   \ 
-3  -1
|   | 
-4  0 
|   | 
-5  1 
|   | 
-6  2

First your Cyclist:

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]

Next the doubly-infinite list:

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]

And then the left-right-list:

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]
回复 原文
栀子花开つ 2024-11-17 13:43:59

当您想要确切的数字时，为什么不直接使用

enumInts :: Integer -> [Integer]
enumInts n = [-(n`div`2)..(n`div`2)]

When you want exactly those numbers, why not just use

enumInts :: Integer -> [Integer]
enumInts n = [-(n`div`2)..(n`div`2)]
回复 原文
淡莣 2024-11-17 13:43:59

虽然它是内置的，但您可以想象列表类型被定义为

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

take 可以这样定义：

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

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

Although it's built-in, you can imagine the list type as being defined as

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

take can be defined like this:

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

You should try to see how you can tweak the definition of take for your own type.

回复 原文
人海汹涌 2024-11-17 13:43:59

我认为这可以解决：

我们的无限数据

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

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

takeOnly n = sort $ take n myList

I think this can be solved as:

Our infinite data

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

getting specific number of elements from this list:

takeOnly n = sort $ take n myList
回复 原文
独﹏钓一江月 2024-11-17 13:43:59

这是我的解决方案：

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

This is my solution:

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

and you can use it that way:

label . forward . backward . forward . forward $ enumInts

where:

label (Elem _ x _) = x
forward (Elem _ _ x) = x
backward (Elem x _ _) = x
回复 原文
~没有更多了~

关于作者

梅窗月明清似水

暂无简介

文章
评论
501 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

Promise

文章 0 评论 0

qq_lbRlsh

文章 0 评论 0

待＂谢繁草

文章 0 评论 0

yy2010hell

文章 0 评论 0

漫无边际

文章 0 评论 0

傲娇萝莉攻

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文