使用 Haskell 字符串时，head$filter 和 head$dropWhile 之间是否存在性能差异？

Question

我正在处理 Haskell 中 "People" 个对象的列表，我想知道 head$dropWhile 和 head$filter 之间的性能是否存在差异以查找第一个有名字的人。两个选项和数据类型的片段是：

datatype Person = Person { name :: String
                         , otherStuff :: StuffTypesAboutPerson }

findPerson :: String -> [Person] -> Person
findPerson n = head $ dropWhile (\p -> name p /= n)
findPerson n = head $ filter (\p -> name p == n)

我的想法是，filter 必须将 n 的全长与每个 name 的全长进行比较，直到找到第一个。我认为 dropWhile 只需要比较字符串直到第一个不匹配的 Char。但是，我知道 Haskell 中有很多神奇之处，尤其是 GHC。我更愿意使用 filter 版本，因为我认为它更易于阅读。但是，我想知道是否真的存在任何性能差异？即使可以忽略不计，我现在从好奇的角度也很感兴趣。

编辑：我知道我还需要防止 Maybe 等错误，但为了简化代码示例，我将其省略。

Answer 1

有几种方法可以解决这个问题

findPerson n = head $ dropWhile (\p -> name p /= n)
findPerson n = head $ filter (\p -> name p == n)
findPerson n = fromJust $ find (\p -> name p == n)

问题也指出了两个事实：

当x,y是相等的字符串时，==需要比较所有的字符
当x,y是不同的字符串时，/=只需要比较到第一个不同的字符

这个是对的，但是没有考虑其他情况

当x,y是相等的字符串时，/=需要比较所有的字符
当x,y为不同的字符串时，==只需要比较到第一个不同的字符

因此，在 == 和 /= 之间没有性能优胜者。我们可以预期，最多，其中一个将执行额外的 not w.r.t。另一个。

此外，所有上述findPerson的三个实现，基本上执行相同的步骤。给定 xs :: [Person]，他们将全部扫描 xs 直到找到匹配的名称，然后不再扫描。在匹配之前的所有人身上，名字将与 n 进行比较，这种比较将在第一个不同的字符处停止（无论我们上面使用什么比较）。匹配的人的名字将与 n 完全比较（同样，在所有情况下）。

因此，这些方法预计会同时运行。它们之间可能存在非常小的差异，但也可能小到难以察觉。如果愿意，您可以尝试使用 criterion 看看会发生什么。

使用 Haskell 字符串时，head$filter 和 head$dropWhile 之间是否存在性能差异？

Is there a performance difference between head$filter and head$dropWhile with Haskell Strings?

performance

haskell

string-comparison