Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Учимся писать факториал

Никогда не думал, что освою конструирование комбинатора неподвижной точки из катаморфизма неподвижной точки единичного функтора.
import Data.Functor.Fixedpoint
import Data.Functor.Identity

fact = cata fact' idfix where
	fact' _ 0 = 1
	fact' (Identity f) x = x * f (x - 1)
        idfix = Fix $ Identity idfix
Из документации:
This abstract nonsense is helpful in conjunction with other category theoretic tricks.

cata :: Functor f => (f a -> a) -> Fix f -> a

A pure catamorphism over the least fixed point of a functor. This function applies the f-algebra from the bottom up over Fix f to create some residual value.
Числа Пеано оказываются неподвижной точкой функтора Maybe:
{-# LANGUAGE NoMonomorphismRestriction #-}
import Data.Functor.Fixedpoint
import Prelude hiding (succ)

type Nat = Fix Maybe

succ = Fix . Just
zero = Fix Nothing

foldNat x y = cata $ maybe x y

toNum = foldNat 0 (+1)

fromNum = ana $ makeMaybe (>0) (-1)

makeMaybe :: (a -> Bool) -> (a -> a) -> a -> Maybe a
makeMaybe cond f x 
	| cond x = Just (f x)
	| otherwise = Nothing
На фолднате факториал пишется по-детсадовски - может можно и без туплов, я не знаю:
add a = foldNat a succ
mul a = foldNat zero (add a)

fact = toNum . fst . foldNat (succ zero,succ zero) (\(x, y) -> (mul x y, succ y)) . fromNum
Бесконечные стримы - это неподвижная точка функтора частично примененного тапла (,) a, а списки - неподвижная точка функтора data PreList a b = PreCons a b | PreNil, изоморфного Maybe (a,b).
Tags: fp, programming
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 9 comments