Haskell Monad Функции

Question

Я прохожу учебное пособие по Хаскеллу, и мне дают этот фрагмент кода, связанный с перемещением коня в шахматах:

import Control.Monad

type KnightPos = (Int,Int)

moveKnight :: KnightPos -> [KnightPos]  
moveKnight (c,r) = do  
    (c',r') <- [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)  
               ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)  
               ]  
    guard (c' `elem` [1..8] && r' `elem` [1..8])
    return (c',r')

in3 :: KnightPos -> [KnightPos]
in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start 

Упражнение состоит в том, чтобы изменить функции так, чтобы canReachIn3 сообщал вамкакие шаги вы можете предпринять, чтобы добраться до конечной позиции, если это возможно.

В этом уроке практически нет упражнений, поэтому у меня возникли проблемы с такими базовыми вещами, как эта ... Я думал об изменениивозвращаемые значения всех 3 функций в [[KnightPos]], где 1 большой список содержит список для каждого возможного упорядочения ходов.Это, вероятно, может привести к тому, что moveKnight будет иметь параметр [KnightPos] вместо KnightPos, что приведет к победе над всей точкой монад, верно?

Любая помощь / мысли будут высоко оценены, спасибо.

Answer 1

Может оказаться полезным немного отойти от концепции Monad, подумав об этом коде, если вы обнаружите, что простые старые операции со списками более естественны для вас. Таким образом, вы можете переписать пример кода (с небольшой очисткой для удобочитаемости) как:

type KnightPos = (Int,Int)

moveKnight :: KnightPos -> [KnightPos]  
moveKnight (c,r) = filter legal candidates where
    candidates = [(c+2,r-1), (c+2,r+1), (c-2,r-1), (c-2,r+1),
                  (c+1,r-2), (c+1,r+2), (c-1,r-2), (c-1,r+2)]
    legal (c',r') = c' `elem` [1..8] && r' `elem` [1..8]

in3 :: KnightPos -> [KnightPos]
in3 start = concatMap moveKnight (concatMap moveKnight (moveKnight start))

canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start

Секретный соус в concatMap. Как вы, наверное, уже знаете, это синоним >>= в монаде List, но сейчас может быть более полезным думать о ней как о сопоставлении функции типа KnightPos -> [KnightPos] со списком [KnightPos] для получения списка списков [[KnightPos]], а затем свести результат обратно в один список.

Хорошо, теперь, когда мы на данный момент обошлись без монад, давайте вернемся к загадке ... Допустим, ваш начальный KnightPos равен (4,4), и вы хотите отслеживать все возможные последовательности ходов из эта позиция. Итак, определите синоним другого типа:

type Sequence = [KnightPos]

Тогда вам нужно, чтобы moveKnight работал с этими последовательностями, находя все возможные ходы из последней позиции в последовательности:

moveKnight :: Sequence -> [Sequence]

Итак, начиная с последовательности [(4,4)], мы получили бы список последовательностей: [[(4,4), (6,3)], [(4,4), (6,5)], [(4,4), (2,3)], ... ]. Тогда я думаю, что единственное изменение, которое вам нужно внести в in3, это соответственно исправить сигнатуру типа:

in3 :: Sequence -> [Sequence]

Я не думаю, что реальная реализация изменится. Наконец, вам нужно, чтобы canReachIn3 выглядел примерно так:

canReachIn3 :: KnightPos -> KnightPos -> [Sequence]

Я намеренно оставляю здесь детали реализации, поскольку не хочу полностью разрушать для вас загадку, но надеюсь, что проиллюстрировал здесь то, что нет ничего особенно «особенного» о списке, или список списков, или что-то еще. Все, что мы действительно сделали, это заменили функцию типа KnightPos -> [KnightPos] новой функцией типа Sequence -> [Sequence] - практически такой же формы. Поэтому заполните реализации каждой функции, используя любой стиль, который кажется вам естественным, а затем, как только он заработает, вернитесь к монадическому стилю, заменив concatMap на >>= и т. Д.

Answer 2

Я бы предложил сделать KnightPos структурой данных, способной содержать не только текущее зелье, но и KnightPos, из которого оно получено:

data KnightPos = KnightPos {history :: Maybe KnightPos, position :: (Int,Int) }

Затем необходимо реализовать уравнение иПоказать классы и исправить moveKnight, чтобы он возвращал эту структуру с соответствующей историей:

moveKnight :: KnightPos -> [KnightPos]  
moveKnight p@KnightPos{position = (c,r)} = do  
    (c',r') <- [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)  
               ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)  
               ]  
    guard (c' `elem` [1..8] && r' `elem` [1..8])
    return $ KnightPos (Just p) (c',r') 

Убедитесь, что вы понимаете последнюю строку этой функции.

Функция in3 теперь должен работать без изменений.Я написал новую функцию pathIn3 :: KnightPos -> KnightPos -> [[KinghtPos]], которая возвращает все возможные пути от start до end в 3 монадических выражениях.

Оповещение о спойлере

Answer 3

"Это, вероятно, будет включать в себя moveKnight, имеющий параметр [KnightPos] вместо KnightPos one ..." Нет, ты бы не хотел этого делать. Сохраняйте функции как можно более простыми.

"... что тогда победит весь смысл монад, верно?" Ну, если вам нужны все порядки ходов, вы просто не в каждом шаге используете join, подразумеваемый в >>=. Вы можете определить функцию, возвращающую список всех путей длины n из заданной начальной точки, где мы можем реализовать эти пути как список пройденных позиций по причинам эффективности в обратном порядке.

waysFrom :: KnightPos -> Int -> [[KnightPos]]

Сначала за один ход (или ноль)

waysFrom start 0 = [[start]]
waysFrom start 1 = map (\t -> [t, start]) $ moveKnight start

, а затем для произвольного числа ходов, в этот момент вы можете использовать снова, используя >>=, чтобы присоединить триподобную структуру, полученную в результате простой рекурсии к списку списков ходов:

waysFrom start n = waysFrom start (n-1) >>= (\w -> [t:w | t<-moveKnight$head w])

, может быть, есть лучший способ сделать это, но это на самом деле не "победит" весь смысл монад.

Answer 4

Я читаю учебник, и мое решение немного изменить функции in3 и canReachIn3

in3 :: KnightPos -> [[KnightPos]]
in3 start = do
    first <- moveKnight start
    second <- moveKnight first
    third <- moveKnight second
    return [start, first, second, third]

canReachIn3 :: KnightPos -> KnightPos -> [[KnightPos]]
canReachIn3 start end = filter (elem end) $ in3 start

Результат in3 содержит список всех возможных путей.