функции высшего порядка для решения загадок в haskell - PullRequest
Новая
       13

функции высшего порядка для решения загадок в haskell

0 голосов
/ 03 декабря 2018

Я пытаюсь воссоздать загадку с пирамидой:

Illustration 1

Последний слой пирамиды - это перестановка чисел от 1 до nгде n - количество полей.Тогда каждое другое поле, которое не находится в нижнем слое, является суммой чисел по диагонали под этим числом.

Итак, я хочу создать функцию, которая при задании загадки слева возвращает решения справа.Я планировал сделать это, перечислив слои следующим образом:

Enumerating Pyramid

для слоев, которые я сделал пользовательским типом данных: 

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

Эта функция помечает 6-е и 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 в кодевыше

1 Ответ

0 голосов
/ 03 декабря 2018

Я бы немного упростил это.Слой - это список чисел: 

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]]

A правильное решение - это решение, которое проверяет данную загадку: 

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]]
...