用 Haskell 解决那些略显愚蠢的面试题

Silly job interview questions in Haskell

Source | HN Comments

文章通过Haskell语言解决常见的面试编程题，如回文判断、Fizz Buzz、求和为N、判断字符串是否为anagrams、求最大最小值、单词频率统计等。文章展示了Haskell简洁的语法、函数式编程的特性，如模式匹配、高阶函数、可组合性、lazy特性等，并对比了Haskell与其他语言的差异。文章还探讨了不同解法的优缺点，以及如何处理空列表等边界情况，强调了Haskell的安全性。

用 Haskell 解决那些略显愚蠢的面试题

作者：Chris Penner，发布于 2020 年 10 月 14 日

标签：haskell

今天我想有趣地看看一些常见且简单的 Haskell "面试题"。这些问题通常用于确定某人是否具备编程和解决问题的能力，我认为让大家了解这些问题在 Haskell 中的表现可能很有用，因为我们所喜爱的语言的解决方案往往遵循与大多数其他语言不同的范例。我将保留对这些问题在确定编程技能方面是否有任何帮助的任何判断 😅；请不要因此而 @ 我。

回文

让我们从标准“是否是回文”问题开始！任务是编写一个函数，该函数确定给定的字符串是否是回文（即，正反读取是否相同）。

isPalindrome :: String -> Bool
isPalindrome str = str == reverse str

>>> isPalindrome "racecar"
True

>>> isPalindrome "hello world!"
False

搞定！关于这一点没什么好说的，很高兴我们的定义大致符合描述问题的英语句子“给定的字符串是否等于其反向字符串”。我将把它作为读者的练习，以扩展它来处理大小写差异，无论您喜欢哪种方式。

Fizz Buzz

接下来是臭名昭著的 Fizz Buzz！对于你们中不熟悉的 3 个人，对于从 1 到 100 的每个数字，如果它能被 3 整除，我们需要打印出“Fizz”，如果它能被 5 整除，则打印“Buzz”，如果它能被 3 和 5 整除，则打印“Fizz Buzz”！否则，我们打印数字本身。让我们看看！

import Data.Foldable

fizzle :: Int -> String
fizzle n
  | n `mod` 3 == 0 && n `mod` 5 == 0 = "Fizz Buzz!"
  | n `mod` 3 == 0 = "Fizz!"
  | n `mod` 5 == 0 = "Buzz!"
  | otherwise = show n

main :: IO ()
main = do
  for_ [1..100] (putStrLn . fizzle)


>>> main
1
2
Fizz!
4
Buzz!
Fizz!
7
8
Fizz!
Buzz!
11
Fizz!
13
14
Fizz Buzz!
16
-- ...you get the idea

我在这里编写了一个辅助函数“fizzle”，它将一个数字转换为其适当的字符串，这样我就可以将“打印”逻辑分开，这在 Haskell 中是一种好的编程风格，因为它使事情更容易测试和推理。

我们可以看到“case analysis”对于这类问题非常有帮助，我正在使用“pattern guards”来做一个类似多路 if 语句的事情。由于“能被 3 和 5 整除”与其他条件重叠，并且也是限制性最强的，因此我们首先检查该条件，然后检查其他两个条件，退回到返回数字本身的字符串版本。一切都运作得非常完美！

我真的很喜欢将这个问题作为一个例子，说明 Haskell 与其他语言的不同之处。 Haskell 中的大多数东西都是函数，即使我们的循环也只是高阶函数！这样做的好处是，函数是 可组合的 并且具有非常清晰的边界，这意味着我们不需要将 for-loop 的语法与我们的逻辑混在一起。正是这些相同的原则使我们能够轻松地将 effectful 打印逻辑与计算输出字符串的函数分开。

我们可以看到的下一个区别是我们使用模式匹配，特别是“pattern guards”，它允许我们选择要使用的函数的哪个定义。它看起来有点像一个美化的 if 语句，但我发现一旦你习惯了它，它的语法噪音就会减少，并且 pattern guards 可以做更多的事情！

剩下的就是循环遍历所有数字并将它们一个一个地打印出来，这要归功于 for_ 函数，这非常容易！下一个！

总和为 N 的问题

这是一个不太常见的问题，但我仍然听过几次！我想它在我过去的一个算法作业中...

任务是获取一个 数字列表 并找到 3 个数字 的任何组合，这些数字的总和达到指定的总数。例如，如果我们想确定总和为 15 的 3 个数字的所有组合，我们希望我们的结果看起来像这样：

>>> sumToN 15 [2, 5, 3, 10, 4, 1, 0]
[[2,3,10],[5,10,0],[10,4,1]]

请注意，每个内部列表的总和都为 15？我们只关心这里的组合，而不是排列，所以我们有 [2, 3, 10]，但不要费心 [3, 2, 10]！

那么我们将如何着手实现一个算法呢？好吧，首先想到的是我们正在寻找组合，然后我们正在过滤它们以匹配一个谓词！

在 Haskell 中，我们喜欢将问题分解为更小的可组合部分，过滤器部分应该很容易，所以让我们先解决组合问题。

快速浏览一下 hackage 后，看起来确实有一个 permutations 函数，但奇怪的是没有 combinations 函数！我想我们可以尝试以某种方式删除 permutations 的输出，但编写我们自己的版本会很有趣！ combinations 非常适合递归计算，所以让我们试试这种方法！

combinations :: Int -> [a] -> [[a]]
-- Only one way to get zero things
combinations 0 _ = [[]]
combinations n (x:xs) =
  -- Get all combinations containing x by appending x to all (n-1)
  -- combinations of the rest of the list
  fmap (x:) (combinations (n-1) xs)
  -- Combine it with all combinations from the rest of the list
   <> combinations n xs
-- No elements means no combinations!
combinations _ [] = []

在这里，我们使用模式匹配和递归来完成我们的脏活。首先，我们可以自信地说，从任何元素列表中获取 0 个元素只有一种方法，所以我们可以填写它。接下来，我们将处理一个步骤，如果我们在列表中至少还有一个元素，我们可以通过将其添加到列表中剩余部分的大小为 n-1 的所有组合来计算包含该元素的所有组合；并且我们将它与列表 其余部分 的所有组合连接起来。

最后，我们添加另一个模式匹配，它处理所有无效输入（无论是负数还是空列表），并简单地断言它们没有有效的组合。

让我们在继续下一部分之前尝试一下我们的实现。

>>> combinations 3 [1..5]
[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]
>>> combinations 2 [1..4]
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

请随意花时间说服自己这些是正确的 😀

为了完成它，我们需要找到这些组合中的任何一个，它们的总和达到我们的目标数字。

sumNToTotal :: Int -> Int -> [Int] -> [[Int]]
sumNToTotal n totalNeeded xs =
  filter matchesSum (combinations n xs)
 where
  matchesSum ys = sum ys == totalNeeded


>>> sumNToTotal 3 15 [2, 5, 3, 10, 4, 1, 0]
[[2,3,10],[5,10,0],[10,4,1]]

太棒了！我们可以简单地获取所有可能的组合，并过滤掉那些不能正确求和到预期数字的结果。另一个巧妙的事情是，因为 Haskell 是 lazy，如果我们只需要找到 第一个 有效组合，我们可以只获取列表的第一个结果，Haskell 不会做任何比绝对必要的更多的工作。

但是等等！这个问题还有一个令人惊讶的 第二部分：

我们现在必须找到总和达到目标数字的任何长度的所有组合，幸运的是，这对我们来说很容易适应！

sumAnyToTarget :: Int -> [Int] -> [[Int]]
sumAnyToTarget totalNeeded xs
 = foldMap (\n -> sumNToTotal n totalNeeded xs) [0..length xs]

>>> sumAnyToTarget 15 [2, 5, 3, 10, 4, 1, 0]
[ [5,10]
, [2,3,10]
, [5,10,0]
, [10,4,1]
, [2,3,10,0]
, [10,4,1,0]
, [2,5,3,4,1]
, [2,5,3,4,1,0]
]

这个新版本重用了我们在上一步中编写的 sumNToTotal 函数！它迭代了每个可能的组合长度，并使用 sumNToTotal 找到所有获胜的组合，然后使用 foldMap 连接它们！如果我这样说，它运作得非常干净！

检查两个字符串是否是 anagrams

出于某种原因，面试官喜欢字符串操作问题；所以让我们再试一个！

在这里，我们的任务是确定两个字符串是否是彼此的 anagrams。我会说这个问题的难度来自于想出你的策略，而不是实现本身。这是我如何在 Haskell 中尝试一下的方法！

import Data.Function (on)
isAnagram :: String -> String -> Bool
isAnagram = (==) `on` sort

>>> isAnagram "elbow" "below"
True
>>> isAnagram "bored" "road"
False
>>> isAnagram "stressed" "desserts"
True

在这里，我们使用了一个时髦的高阶函数 on； on 接受两个函数，然后再接受两个参数！在这种情况下，它在两个参数上调用“sort”，然后检查排序后的结果是否相等！事实证明，这足以知道两个字符串是否是 anagrams！

但是等等！那是什么？如果它们的大小写不同怎么办！好的，没问题！

import Data.Char (toLower)

isAnagram :: String -> String -> Bool
isAnagram a b = (==) `on` (sort . map toLower)

现在满意了吗？没有？那是什么？它似乎没有性能？好吧，是的，但实际上不是！

虽然 sort 具有 O(nlogn) 性能配置文件是正确的，但这里有趣的一件事是，排序在 Haskell 中是 lazy 的！这意味着如果我们的两个字符串不相等，它们只会排序到足以确定不相等！事实上，如果每个排序字符串的第一个元素彼此不相等，那么我们就不会费心进行更多排序。

当然，我们的函数并不完美，但还不错，特别是自从这是首先想到的方法以来。将我们的 2 行解决方案与 Java Solution 进行比较，该帖子给了我这个问题的想法。它可能更有效（虽然说实话我没有对它们进行基准测试），但如果我将来经常阅读这段代码，我更喜欢以足够的水平执行的最清晰的版本。

最小值和最大值

这是一个问题！给定一个元素列表，找到该列表的最小和最大元素！

我将展示并讨论三种不同的策略。

这是第一个：

simpleMinMax :: Ord a => [a] -> (a, a)
simpleMinMax xs = (minimum xs, maximum xs)

>>> simpleMinMax [3, 1, 10, 5]
(1,10)

这是我们可以想象到的最简单的方法来完成这类事情；而且它确实有效！不幸的是，在这个壁橱里隐藏着一些来自“legacy” Haskell 的骨架。看看如果我们尝试在一个空列表上使用它会发生什么！

>>> simpleMinMax []
(*** Exception: Prelude.minimum: empty list

糟糕... Haskell 不应该抛出异常！不过没关系，还有一些其他好的方法可以实现这一点，而不会让我们崩溃！

是时候进行下一个了！

boundedMinMax :: (Bounded a, Ord a) => [a] -> (a, a)
boundedMinMax xs = coerce $ foldMap (\x -> (Min x, Max x)) xs

>>> boundedMinMax [4, 1, 23, 7] :: (Int, Int)
(1,23)
>>> boundedMinMax [] :: (Int, Int)
(9223372036854775807,-9223372036854775808)

如果你没有学到足够关于 Semigroups 和 Monoids 的知识，这个实现可能会有点令人困惑，但不要让这吓到你！这些都是 Haskell 中非常常见的抽象概念，并且经常被使用并产生很大的效果！

Semigroup 是一种接口类型，它提供了一种实现，使我们可以将多个元素组合在一起。 Haskell 有两个 semigroup 类型包装器，它们为我们包装的任何类型提供特定的行为：Min 和 Max！

这些类型定义了一个组合操作，无论何时我们组合两个元素，都将仅保留最小或最大值！我在这里使用 foldMap 将每个列表元素投影到这两种类型的元组中，当列表被 foldMap 折叠时，它们将全部组合在一起，并将包括最低和最高的元素，所有这些都在一次传递中！

那么第二个例子是怎么回事？好吧，这有点出乎意料，但并不一定错误。当我们缺少任何要比较的元素时，foldMap 将使用我们每个类型包装器的默认值，如果它们是 monoids，它可以这样做。对于 Min 和 Max，默认值是被包装类型的“最小”和“最大”值，它由我们在类型签名中要求的 Bounded 接口定义。这运作良好，并且在 大多数 情况下按预期运行，但也许我们可以再尝试一次：

import Data.Semigroup

minMax :: Ord a => [a] -> Maybe (a, a)
minMax xs = case foldMap (\a -> Just (Min a, Max a)) xs of
        Just (Min x, Max y) -> Just (x, y)
        _ -> Nothing

>>> minMax [4, 1, 9, 5]
Just (1,9)
>>> minMax []
Nothing

好的！这几乎相同，但我们需要一种显式的方法来正确处理一个空值列表。在这种情况下，通过将我们的元组包装在 Just 中，我们调用 Maybe monoid，并且请记住，如果我们的列表为空，foldMap 足够聪明地返回该 monoid 的“空”元素！这意味着如果没有元素，我们将得到 Nothing。

起初这可能看起来像“魔法”，但所有这些 typeclasses 都有 laws，这些 laws 规定了它们的行为并使它们可预测。我建议你有时间多了解一下 monoids，它们既迷人又有用！

这是一个非常“安全”的实现，事实上比大多数语言提供的要安全得多。我们在列表为空的情况下显式返回 Nothing，并且 Maybe 返回类型要求调用者处理这种情况。我之前提到过函数是可组合的，事实证明数据类型也是如此！如果我们在一个元组中将两个对象与一个 semigroup 配对在一起，那么该元组也有一个 semigroup 实例，当我们组合元组时，它会将各个元素组合在一起！

单词频率

这也是一个非常受欢迎的！

这次的挑战是，给定一个文本块，找到最常见的单词！

最终，这归结为对数据结构的理解。

import Data.List (maximumBy)
import Data.Function (on)
import qualified Data.Map as M

mostCommonWord :: String -> Maybe String
mostCommonWord str =
  if null wordCounts
    then Nothing
    else Just . fst . maximumBy (compare `on` snd) . M.toList $ wordCounts
 where
  wordCounts = M.unionsWith (+) . fmap (\w -> M.singleton w 1) . words $ str

这次发生的事情有点多，所以让我们分解一下！

在 Haskell 中，我们使用 . 进行“数学风格”的函数组合，因此我们从右到左读取大多数表达式。

让我们首先看一下 where 子句中的 wordCounts 绑定。从右到左读取，首先我们使用内置 Prelude 中的 words 函数将传入的流拆分为单词列表，然后我们从每个单词中创建一个键值映射，其中包括单词作为键，值为 1 开始。

现在我们有一个键值映射列表，并且可以使用 Data.Map 库中的 unionsWith 将它们全部按键相加，这将计算每个键的元素数量，并将导致一个键值映射，其中值表示出现次数。

我们现在有了一个映射，所以让我们找到最大的计数！

首先，为了安全起见，我们将检查映射是否根本有任何值，如果没有，那么我们将返回 Nothing。否则，我们可以通过调用 M.toList 将映射转换为键值对列表，然后我们可以使用 maximumBy 根据我们指定的比较函数返回最大的元素！ on 在这里派上用场，我们可以告诉它比较第二个元素，即计数。这将返回给我们具有最大值的键值对，然后我们只需要使用 fst 获取键作为结果！

最终，这是一个有点幼稚的实现，在巨大的文本上效果不佳，但它应该足以让你通过面试的白板部分😄。

总结

这就是我今天为您准备的全部内容，我确定没有什么革命性的东西，但希望您玩得开心，或者可能学到了一两件关于代码在 Haskell 中与您喜欢的语言相比是什么样子的知识😄

希望你学到了一些东西🤞！如果你这样做了，请考虑查看我的书：它教授在 Haskell 和其他函数式编程语言中使用 optics 的原则，并带你从初学者到各种 optics 的向导！你可以在这里获得它。每次销售都有助于我证明更多时间编写像这样的博客文章是合理的，并帮助我继续编写教育性的函数式编程内容。干杯! Tweet Follow @chrislpenner © 2014-2018 Chris Penner - Feed