1

在学习 Haskell 时，我为自己设置了一个难题，那就是编写一个 4 X 4 KenKen 求解器。这涉及将数字 1 到 4 放置在 4 x 4 矩阵中，这样每一行和每一列都包含不同的值。还有一些笼子根据加法、乘法、除法（仅两个单元格）或减法（仅两个单元格）来限制其中包含的数字。有关完整规则，请参阅KenKen 上的维基百科页面。

我已经进行了 30 年的命令式编程，我想知道如何在 Haskell 中解决这个问题。作为一个绝对的初学者，我在这里需要一些建议。

我的粗略概述：-

  • 目前，只需硬编码约束和任何起始数字，以避免必须学习如何进行 IO 和解析，
  • 暂时将其保持在 4 x 4 以使生活更简单，
  • 将单元格视为Maybe int长度为 16 的不可变列表，
  • 创建一个类型类，constraint它可以获取一个单元格列表并返回一个布尔值是否违反了约束（或者这有点面向对象，我应该为这些创建函数？），
  • 约束会说位置 1、2 和 5 中的单元格必须加起来为 6。函数将获取一个单元格列表，它将返回 true 或 false，
  • 编写加、减、除、乘和唯一的约束，
  • 创建递归solve函数，接收单元格和约束列表，
  • solve将根据每个约束检查单元格，并使用新列表调用自身，尝试不同的数字或回溯

所以我的问题是，这种方法看起来是否可行，并且在 Haskell 中是惯用的吗？你能建议我如何做一些更实用的东西而不需要知道任何太高级的东西。我对这是解决此问题的最有效方法不感兴趣，因为这只是我自己设定的学习练习。

编辑：下面的答案和评论围绕着对类型类的需求，所以这可能是我弄错了。我觉得需要它，这样我就可以多态地处理所有不同类型的约束。我相信每个人都在说这是不够的，我可以只拥有一个接受单元格列表并返回布尔值的函数列表。

4

1 回答 1

3

这听起来不错，但你对约束是函数而不是类型类是正确的。在 haskell 中，接口的工作被分成两部分。处理 this 函数的类型类可以采用实现等式的此接口部分的任何类型。Show 类型类就是一个例子。通过实现 Show 类型类，您的数据类型支持 show (to string) 函数。这意味着 print 现在将打印您的类型的实例。

接口概念的一部分，您实现一个接口以便您可以对同一函数进行多个实现，这是通过高阶函数而不是附加到不同类型的同名函数来处理的。例如，doFunc opp a b = opp a b它将具有类型 (a -> b -> c) -> a -> b -> c。然后这个函数可以接受任何两个操作数函数并像doFunc (+) 1 2or一样应用它doFunc (*) 1 2。

我建议的主要事情是尝试自下而上。我发现它确实有助于构建小函数并将它们构成 FP 编程哲学。

于 2013-10-31T14:30:50.787 回答