Control.Monad.Fix
| Авторские права | (c) Andy Gill 2001 (c) Oregon Graduate Institute of Science and Technology 2002 |
|---|---|
| Лицензия | BSD-стиль (см. файл libraries/base/LICENSE) |
| Поддержка | libraries@haskell.org |
| Стабильность | стабильно |
| Переносимость | переносимо |
| Safe Haskell | Безопасно |
| Язык | Haskell2010 |
Описание
Монадные неподвижные точки.
Для подробного обсуждения см. диссертацию Леванта Эркова «Рекурсия значений в монадных вычислениях» (Oregon Graduate Institute, 2002).
class Monad m => MonadFix (m :: Тип -> Тип) where Исходный код
Монады, имеющие неподвижные точки с семантикой «связывания узлов». Экземпляры MonadFix должны удовлетворять следующим законам:
- Чистота
mfix (return . h) = return (fix h)- Сжатие слева (или Усиление)
mfix (\x -> a >>= \y -> f x y) = a >>= \y -> mfix (\x -> f x y)- Перемещение
-
mfix (liftM h . f) = liftM h (mfix (f . h)), для строгихh. - Вложение
mfix (\x -> mfix (\y -> f x y)) = mfix (\x -> f x x)
Этот класс используется при переводе рекурсивной do нотации, поддерживаемой GHC и Hugs.
Методы
mfix :: (a -> m a) -> m a Исходный код
Неподвижная точка монадного вычисления. mfix f выполняет действие f только один раз, а конечный результат используется в качестве входных данных. Поэтому f не должен быть строгим, иначе mfix f будет расходиться.
Экземпляры
| MonadFix Complex Источник | С версии: base-4.15.0.0 |
Определено в Data.Complex | |
| MonadFix First Источник | С версии: base-4.9.0.0 |
Определено в Data.Semigroup | |
| MonadFix Last Источник | С версии: base-4.9.0.0 |
Определено в Data.Semigroup | |
| MonadFix Max Источник | С версии: base-4.9.0.0 |
Определено в Data.Semigroup | |
| MonadFix Min Источник | С версии: base-4.9.0.0 |
Определено в Data.Semigroup | |
| MonadFix NonEmpty Источник | С версии: base-4.9.0.0 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix Identity Источник | С версии: base-4.8.0.0 |
Определено в GHC.Internal.Data.Functor.Identity | |
| MonadFix First Источник | С версии: base-4.8.0.0 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix Last Источник | С версии: base-4.8.0.0 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix Down Источник | С версии: base-4.12.0.0 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix Dual Источник | С версии: base-4.8.0.0 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix Product Источник | С момента появления: base-4.8.0.0 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix Sum Источник | С момента появления: base-4.8.0.0 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix Par1 Источник | С момента появления: base-4.9.0.0 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix Q Источник |
Если функция, переданная в С момента появления: ghc-internal-2.17.0.0 |
Определено в GHC.Internal.TH.Syntax | |
| MonadFix IO Источник | С момента появления: base-2.1 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix Maybe Источник | С момента появления: base-2.1 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix Solo Источник | С момента появления: base-4.15 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix [] Источник | С момента появления: base-2.1 |
Определено в GHC.Internal.Control.Monad.Fix | |
| MonadFix (ST s) Источник | С момента появления: base-2.1 |
Определено в GHC.Internal.Control.Monad.ST.Lazy.Imp | |
| MonadFix (Either e) Source | Since: base-4.3.0.0 |
Defined in GHC.Internal.Control.Monad.Fix | |
| MonadFix (ST s) Source | Since: base-2.1 |
Defined in GHC.Internal.Control.Monad.Fix | |
| Monoid a => MonadFix ((,) a) Source | Since: base-4.21 |
Defined in GHC.Internal.Control.Monad.Fix | |
| MonadFix f => MonadFix (Ap f) Source | Since: base-4.12.0.0 |
Defined in GHC.Internal.Control.Monad.Fix | |
| MonadFix f => MonadFix (Alt f) Source | Since: base-4.8.0.0 |
Defined in GHC.Internal.Control.Monad.Fix | |
| MonadFix f => MonadFix (Rec1 f) Source | Since: base-4.9.0.0 |
Defined in GHC.Internal.Control.Monad.Fix | |
| (MonadFix f, MonadFix g) => MonadFix (Product f g) Source | Since: base-4.9.0.0 |
Defined in Data.Functor.Product | |
| (MonadFix f, MonadFix g) => MonadFix (f :*: g) Source | Since: base-4.9.0.0 |
Defined in GHC.Internal.Control.Monad.Fix | |
| MonadFix ((->) r) Source | Since: base-2.1 |
Defined in GHC.Internal.Control.Monad.Fix | |
| MonadFix f => MonadFix (M1 i c f) Source | Since: base-4.9.0.0 |
Определено в GHC.Internal.Control.Monad.Fix Методыmfix :: (a -> M1 i c f a) -> M1 i c f a Исходный код |
fix :: (a -> a) -> a Исходный код
fix f — это наименьшая неподвижная точка функции f, т.е. наименее определённая x такая, что f x = x.
Когда f является строгой, это означает, что по определению строгости f ⊥ = ⊥, и таким образом наименьшая неподвижная точка любой строгой функции — ⊥.
Примеры
Мы можем записать функцию факториала, используя прямую рекурсию, как
>>> let fac n = if n <= 1 then 1 else n * fac (n-1) in fac 5 120
Это использует тот факт, что let Haskell’а вводит рекурсивные определения. Мы можем переписать это определение, используя fix,
Вместо вызова рекурсивной функции, мы вводим фиктивный параметр rec; при использовании в fix, этот параметр ссылается на аргумент fix, тем самым рекурсия вводится повторно.
>>> fix (\rec n -> if n <= 1 then 1 else n * rec (n-1)) 5 120
Используя fix, мы можем реализовать версии repeat как fix . (:) и cycle как fix . (++)
>>> take 10 $ fix (0:) [0,0,0,0,0,0,0,0,0,0]
>>> map (fix (\rec n -> if n < 2 then n else rec (n - 1) + rec (n - 2))) [1..10] [1,1,2,3,5,8,13,21,34,55]
Подробности реализации
© The University of Glasgow and others
Licensed under a BSD-style license (see top of the page).
https://downloads.haskell.org/~ghc/9.12.1/docs/libraries/base-4.21.0.0-8e62/Control-Monad-Fix.html
