高阶函数在haskell中解谜函数

Question

我试图重建一个金字塔的谜语:

金字塔的最后一层是从1到n的数字的排列,其中n是字段的数量.然后,不在最低层中的每个其他字段是该数字下对角线的数字的总和.

所以我想做一个函数,当给出左边的谜语时,返回右边的解决方案.我计划通过枚举这样的图层来做到这一点:

对于我制作自定义数据类型的图层:

data Layer = One | Two | Three | Four | Five | Six
deriving (Eq,Ord,Enum,Show)

和其他类型:

type LayerDepth = Layer
type FieldNumber = Int
type FieldContent = Int
type FieldAssignment = (FieldNumber -> FieldContent)
type PyramidRiddle = FieldAssignment
type PyramidSolution = FieldAssignment
type PyramidSolutions = [PyramidSolution]

和功能:

solveRiddle :: LayerDepth -> PyramidRiddle -> Pyramidsolutions

对于图示的例子,我将创建类型的匿名函数(FieldNumber - > FieldContent):

fieldAssignment1 = \n -> if (n==6) || n==8) then 3 else 0

此功能将标记第3和第8个字段,编号为3

然后打电话: solveRiddle Four fieldAssignment1 ->> [pyramidSolution1, pyramidSolution2]

四个意味着四层,而PyramidSolutions是FieldAssignments的列表,它有一个解决方案

我的问题:

我会以某种方式返回一个函数,该函数将给出字段赋值计算最后一层中的排列,并根据该函数将数字分配给其余字段.

不知何故这样:

pyramidSolution1 = \n -> case n of 1 -> 18
                                   2 -> 11 
                                   3 -> 7
                                   4 -> 7 
                                   5 -> 4 
                                   6 -> 3 
                                   7 -> 4 
                                   8 -> 3 
                                   9 -> 1 
                                  10 -> 2
                                   _ -> 0 

和

pyramidSolution2 = \n -> case n of 1 -> 20
                                   2 -> 12 
                                   3 -> 8
                                   4 -> 7 
                                   5 -> 5 
                                   6 -> 3 
                                   7 -> 4 
                                   8 -> 3 
                                   9 -> 2 
                                  10 -> 1
                                   _ -> 0 

但是最好的方法是什么？

如何指定数字的排列并知道如何将它们放在数字上方是下面数字的总和？

在上面的代码中实现匿名函数pyramidSolution1和pyramidSolution2的最佳方法是什么？

Answer 1

我会简化这一点.图层是一个数字列表:

type Layer = [Int]
-- e.g. [4,3,1,2]

规则是一些元素的固定分配列表.

data Must = Any | Only Int  -- Yes, it's just Maybe with different labels

type Rule = [Must]
-- e.g. [Any,Only 3,Any,Any]

你需要一个可以从它下面生成一个图层的函数:

nextLayer :: Layer -> Layer
nextLayer = undefined
-- nextLayer [4,3,1,2] == [7,4,3]

以及根据有效规则检查图层的功能

isLayerValid :: Rule -> Layer -> Bool
isLayerValid = undefined
-- isLayerValid [Any,Any,Only 3] [1,2,3] == True
-- isLayerValid [Any,Any,Only 3] [1,3,2] == False

谜语只是一个规则列表:

type Riddle = [Rule]
riddle :: Riddle
riddle = [[Any, Only 3, Any, Any], [Any, Any, Only 3], [Any, Any], [Any]]

并且解决方案是从某个基础开始的层列表.

type Pyramid = [Layer]
pyramid :: Layer -> Pyramid
pyramid [] = []
pyramid base = base : pyramid (nextLayer base)
-- pyramid [4,3,1,2] == [[4,3,1,2],[7,4,3],[11,7],[18]]

一个正确的解决方案是验证给定的谜语:

isValidFor :: Riddle -> Pyramid -> Bool
isValidFor [] [] = True
isValidFor (r:rs) (x:xs) = isLayerValid r x && isValidFor rs xs
-- isValidFor riddle (pyramid [4,3,1,2]) == True
-- isValidFor riddle (pyramid [1,3,4,2]) == False

现在的诀窍是产生所有潜在的解决方案

permutations :: [Int] -> [[Int]]
permutations ns = undefined

-- e.g. allSolutions = map pyramid (permutations [1..n])

并使用您的解决方案测试过滤它们:

solutions :: Riddle -> [Pyramid]
solutions r = filter (isValidFor r) (map pyramid (permutations [1..length r]))
-- solutions riddle == [pyramid [4,3,1,2], pyramid [4,3,2,1]]