是否存在类似(xs:x)的东西

Question

我是Haskell的新手.我知道我可以reverse通过这样做来创建一个函数:

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = (Main.reverse xs) ++ [x]

是否存在(xs:x)(与列表连接的列表,即x列表中的最后一个元素),以便将最后一个列表元素放在列表的前面？

rotate :: [a] -> [a]
rotate [] = []
rotate (xs:x) = [x] ++ xs

当我尝试编译包含此函数的程序时,我收到这些错误:

Occurs check: cannot construct the infinite type: a = [a]
When generalising the type(s) for `rotate'

Answer 1

我也是Haskell的新手,所以我的答案不具有权威性.无论如何,我会使用last和init:

Prelude> last [1..10] : init [1..10]
[10,1,2,3,4,5,6,7,8,9]

要么

Prelude> [ last [1..10] ] ++ init [1..10]
[10,1,2,3,4,5,6,7,8,9]

Answer 2

简短的回答是:模式匹配不可能,你必须使用一个函数.

答案很长:它不是标准的Haskell,但是如果你愿意使用一个名为View Patterns的扩展,并且如果你的模式匹配没有问题,最终花费的时间超过了恒定的时间.

原因是模式匹配基于结构的构建方式.列表是抽象类型,具有以下结构:

data List a = Empty | Cons a (List a)
           deriving (Show) -- this is just so you can print the List 

当您声明类似的类型时,您将生成三个对象:类型构造函数List和两个数据构造函数:Empty和Cons.类型构造函数接受类型并将它们转换为其他类型,即List获取类型a并创建另一种类型List a.数据构造函数就像一个返回类型的函数List a.在这种情况下,你有:

Empty :: List a

代表一个空列表和

Cons :: a -> List a -> List a

它获取类型a和列表的值,并将值附加到列表的头部,返回另一个列表.所以你可以建立这样的列表:

empty = Empty         -- similar to []
list1 = Cons 1 Empty  -- similar to 1:[] = [1]
list2 = Cons 2 list1  -- similar to 2:(1:[]) = 2:[1] = [2,1]

这或多或少是列表的工作方式,但取而代之的是Empty你所拥有的[]和代替Cons你的(:).当你输入类似[1,2,3]这样的东西时,1:2:3:[]或者仅仅是语法糖Cons 1 (Cons 2 (Cons 3 Empty)).

进行模式匹配时,您正在"解构"该类型.了解类型的结构使您可以对其进行独特的反汇编.考虑功能:

head :: List a -> a
head (Empty) = error " the empty list have no head"
head (Cons x xs) = x

类型匹配上发生的是数据构造函数与您给出的某些结构匹配.如果匹配Empty,则表示您没有空列表.如果匹配Const x xs则x必须具有类型a并且必须是列表的头部并且xs必须具有类型List a并且是列表的尾部,因为这是数据构造函数的类型:

Cons  :: a -> List a -> List a

如果Cons x xs是类型List a不是x必须a和xs 必须List a.(x:xs)也是如此.如果你在GHCi中查看(:)的类型:

> :t (:) 
 (:) :: a -> [a] -> [a]

因此,如果(x:xs)是类型[a],则x必须是a且xs必须是[a].您尝试执行此操作(xs:x)然后xs像列表一样处理时收到的错误消息正是因为这个原因.通过使用(:)编译器推断出xs具有类型a,并通过您的使用 ++,它推断出xs必须是[a].然后,它怪胎原因没有有限型a为其中a = [a]-这就是他想告诉你与该错误消息.

如果您需要以与数据构造函数构建结构的方式不匹配的其他方式反汇编结构,那么您必须编写自己的函数.标准库中有两个函数可以执行您想要的操作:last返回列表的最后一个元素,并init返回列表中所有但最后的元素.

但请注意,模式匹配在恒定时间内发生.要找出列表的头部和尾部,列表的长度无关紧要,您只需要查看最外层的数据构造函数.找到最后一个元素是O(N):你必须挖掘,直到找到最里面Cons或最里面(:),这需要你"剥离"结构N次,其中N是列表的大小.

如果您经常需要查找长列表中的最后一个元素,您可能会考虑使用列表是否是一个好主意.您可以继续Data.Sequence(对第一个和最后一个元素的恒定时间访问),Data.Map(log(N)如果您知道其键,则可以访问任何元素),Data.Array(如果您知道其索引,则可以对元素进行恒定时间访问),Data.Vector或者符合您需求的其他数据结构比列表更好.

好.这是简短的答案(:P).你需要自己查找一个长的,但这是一个介绍.

通过使用视图模式,您可以使用非常接近模式匹配的语法.视图模式是一种扩展,您可以将其作为代码的第一行使用:

{-# Language ViewPatterns #-}

有关如何使用它的说明,请访问:http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns

使用视图模式,您可以执行以下操作:

view :: [a] -> (a, [a])
view xs = (last xs, init xs)

someFunction :: [a] -> ...
someFunction (view -> (x,xs)) = ...

比x和xs将被绑定到last和init你提供的清单someFunction.在语法上它感觉像模式匹配,但它实际上只是应用last和init给定的列表.

Answer 3

如果你愿意使用的东西从普通列表不同,你可以有一个看Seq的容器封装类型,如记录在这里.它有O(1)缺点(前面的元素)和snoc(后面的元素),并允许通过使用视图来匹配前面和后面的元素.