Как написать функцию с фиксированной точкой в ​​haskell

Question

У меня есть функция со следующей подписью:

simCon :: [Constraint] -> Maybe [Constraint]

Я хотел бы написать метод, который, в случае simCon возвращает Just [Constraint]Я хочу передать их обратно в simCon и повторно запустить метод, и продолжать делать это, пока ввод не совпадет с выводом.

В случае Ничего, я хотел бы прекратить алгоритм.

У меня есть что-то, что будет работать, если оба входа и выхода одного типа

fixed :: Eq a => (a -> a) -> a -> a
fixed f a 
  | a == a' = a
  | otherwise = fixed f a'
  where a' = f a

Но это не сработает, потому что сейчас я возвращаю "Может быть". Может кто-нибудь предложить способ написать аналогичную функцию, но для возвращаемого типа Maybe?

Answer 1

Мы можем использовать функцию связывания здесь:

import Data.Bool(bool)
import Control.Monad(liftM2)

fixedM :: (Eq a, Monad m) => (a -> m a) -> a -> m a
fixedM f = go
    where go x = f x >>= (liftM2 bool go pure <*> (x ==))

Более подробная реализация:

fixedM :: (Eq a, Monad m) => (a -> m a) -> a -> m a
fixedM f x = do
    x' <- f x
    if x == x'
        then pure x'
        else fixedM f x'

Таким образом, мы сначала рассчитаем x' с участием f x, В случае f x вернуть Just x', тогда мы продолжим. В случае f x вернуть Nothing, fixedM вернусь Nothing также. Затем мы сравниваем x с участием x', В случае равенства двух мы возвращаем pure x'иначе мы вернемся на fixedM f x',

В качестве альтернативы, мы можем использовать сопоставление с образцом, хотя это в основном делает оператор связывания явным (и работает только для Maybe):

import Control.Monad(ap)

fixedM :: Eq a => (a -> Maybe a) -> a -> Maybe a
fixedM f = ap go f
    where go x (Just x') | x == x' = go x' (f x')
                         | otherwise = Just x'
          go _ _ = Nothing

мы можем сделать его более компактным, используя шаблонную защиту:

fixedM :: Eq a => (a -> Maybe a) -> a -> Maybe a
fixedM f = go
    where go x | Just x' <- f x = bool (go x) (Just x) (x == x')
               | otherwise = Nothing