Haskell新手在将列表拆分为一半时出现问题

Question

这是我尝试编写一个函数,将偶数长度列表分成两个相等的一半.

halve :: [a] -> ([a], [a])
halve x 
   | even len = (take half x, drop half x)
   | otherwise = error "Cannnot halve a list of odd length"
   where
      len = length x
      half = len / 2

我收到以下错误:

 No instance for (Fractional Int) arising from a use of ‘/’
    In the expression: len / 2
    In an equation for ‘half’: half = len / 2
    In an equation for ‘halve’:

我不明白错误,但我怀疑Haskell需要提前告知len是你可以除以2的东西.那么,我该如何纠正这个例子呢？我的代码是否接近惯用的haskell？我很感激有关我的代码的任何其他意见.

Answer 1

该/用于当你高兴有一个非整数的答案.由于你已经检查了数字的偶数,你可以使用整数除法div:

halve :: [a] -> ([a], [a]) 
halve x | even len = (take half x, drop half x) 
        | otherwise = error "Cannnot halve a list of odd length" 
   where len = length x 
         half = len `div` 2

(就个人而言,我很乐意将不完整的奇数长度列表减半并避免出现错误消息,但这取决于您.)

这种区别由以下类型表示:

(/) :: Fractional a => a -> a -> a
div :: Integral a => a -> a -> a 

所以你只能/在类型支持非整数除法时使用,并且只能div在它是整数类型时使用.这样你就不会错误地认为你在做另一种分裂时正在进行某种分裂.

干得好,顺便说一下,你在思考问题.

"没有......的实例"

实际上,"No instance for ..."错误消息几乎总是因为某些东西是错误的类型.当我以错误的顺序输入参数时,我经常得到它.在这种情况下,当你键入时,你已经拥有了使用其他类型的divition Int.

它表示"无实例",因为您尝试使用的函数适用于一类类型,但您提供的数据类型不在该类的(实例)中.编译器将此视为缺少的实例声明,通常情况下,这只是一个错误而且它是完全错误的类型.我很少打算将某个实例作为一个类的实例然后忘记,而我经常把参数放在错误的地方.

Answer 2

length函数的类型签名是[a] -> Int; 这告诉你length返回一个Int.

此外,/运营商(类型签名Fractional a => a -> a -> a)仅与具有Fractional实例的类型兼容; 因为没有Fractional实例存在Int,所以你不允许写类似的东西

length x / 2

使用div(签名类型Integral a => a -> a -> a)函数执行整数除法:

div len 2

此外,有一些方法可以改善你的实施halve.

1. 而不是(take half x, drop half x),你可以使用splitAt half x,只需要一次通过x.

2. 这是一个更自然的实现(这是卡片玩家所做的!)和更高效(不需要计算长度):

   halve :: [a] -> ([a], [a])
   halve []  = ([], [])
   halve [x] = ([x], [])  -- just in case of a list of odd length
   halve (x : y : zs) = (x : xs, y : ys)
     where
       (xs, ys) = halve zs
   

Answer 3

请注意，将列表减半可以在结构上完成，而无需任何索引。并行遍历列表两次，一次遍历的速度是另一遍的两倍。当较快的速度触底时，较慢的速度达到一半。

halve :: [a] -> ([a], [a])
halve [] = ([],[])
halve xs = go xs xs
  where
    go (x:xs) (_:_:ys) = let (first,last) = go xs ys in (x:first, last)
    go (x:xs) [_] = ([x],xs)
    go (x:xs) []  = ([],x:xs)

对于go奇数长度的列表，第二个子句是“平局”。照原样，代码将奇数1放在上半部分的末尾。([],x:xs)如果您愿意，只需将右侧更改为即可。

这个想法是Danvy和Goldberg（http://www.brics.dk/RS/05/3/BRICS-RS-05-3.pdf）所确定的“再来一次”模式的关键。