手动实现 Haskell 中的整数除法

Question

对于Haskell中的家庭作业，我想实现二分查找，但不允许使用任何预定义的函数。

我正在苦苦挣扎的是实现一种有效查找列表中间元素的方法，所以基本上我想计算

(length x) `div` 2

对于某些给定的列表 x。

我能想到的唯一实现是

halfOf :: Int -> Int
halfOf 0 = 0
halfOf 1 = 0
halfOf x = 1 + halfOf (x - 2)

但这太慢了。有没有一些更快的方法可以在不使用任何预定义函数的情况下实现它？

提前致谢。

Answer 1

如果我打算在不使用 length 或 div 的情况下尝试这样做，这就是我会做的。第 1 步是“有效地”将长度减半；在第二步中，我们将确保我们也有正确的元素。

halfAsLong :: [a] -> [a]
halfAsLong (x:y:rest) = x:halfAsLong rest
halfAsLong short = short

一旦我们有了它，我们就可以使用它通过一次迭代列表及其一半长度的对应物来在中间点拆分列表¹。

splitLength :: [a] -> [b] -> ([b], [b])
splitLength (a:as) (b:bs) = let (pre, post) = splitLength as bs in (b:pre, post)
splitLength _ bs = ([], bs)

我们现在可以将两者结合起来。

halfsies :: [a] -> ([a], [a])
halfsies as = splitLength (halfAsLong as) as

试试看：

> mapM_ (print . halfsies) ["", "a", "ab", "abc", "abcd", "abcdefghijklmnopqrstuvwxyz"]
("","")
("a","")
("a","b")
("ab","c")
("ab","cd")
("abcdefghijklm","nopqrstuvwxyz")

¹ 实际上，如果我这样做，而不是试图教初学者，我至少会使用惰性模式：

... let ~(pre, post) = splitLength ... in ...

并且可能还尝试使用差异列表来查看它是否更快：

splitLength = go id where
    go pre (a:as) (b:bs) = go (pre . (b:)) as bs
    go pre _ bs = (pre [], bs)

如果 id 和 (.) 算作“预定义函数”，我会自己定义副本或只使用它们代表内联的 lambda。

手动实现 Haskell 中的整数除法

Implementing Integer Division in Haskell by Hand

haskell

functional-programming

division