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 ...”错误消息几乎总是因为类型错误。当我以错误的顺序放置参数时，我经常会得到它。在这种情况下，当类型为Int时，您将使用其他排序方式。

它表示“无实例”，因为您要使用的函数适用于一类类型，但是您提供的数据类型不在该类（的实例中）。编译器将其视为缺少的实例声明，在大多数情况下，这只是一个错误，而且完全是错误的类型。我很少打算将某个东西作为类的实例然后忘了，而我经常将参数放在错误的位置。

Answer 2

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

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）所确定的“那里又回来”模式的关键的一半。

Answer 3

length函数的类型签名为[a] -> Int；这告诉您length返回Int。

此外，/运算符（类型为Fractional a => a -> a -> a的类型）仅与具有Fractional实例的类型兼容；因为no Fractional instance exists for Int，您不允许写类似

的内容

Fractional

使用Int函数（类型为length x / 2 的类型）执行整数除法：

div

---

此外，还有多种方法可以改善Integral a => a -> a -> a的实现。

1. 您可以使用div len 2 代替halve，它只需要通过(take half x, drop half x)一遍。

2. 这是一种更自然的实现（这是纸牌玩家的工作！），并且效率更高（无需计算长度）：

   splitAt half x

Answer 4

[x和

halve :: [a] -> ([a], [a])
halve []  = ([], [])
halve [x] = ([x], [])  -- necessary case for input lists that contains an odd number of elements
halve (x : y : zs) = (x : xs, y : ys)
  where
    (xs, ys) = halve zs

]期望使用take类型的参数。 drop执行分数除法，因此其结果不能为Int类型。使用(/)进行整数除法：

Int