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

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

5 голосов
/ 21 июня 2019

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

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?

1 Ответ

4 голосов
/ 21 июня 2019

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

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