data-fix (empty) → 0.0.1

raw patch · 4 files changed

+170/−0 lines, 4 filesdep +basesetup-changed

Dependencies added: base

Files

• LICENSE +30/−0
• Setup.hs +3/−0
• data-fix.cabal +31/−0
• src/Data/Fix.hs +106/−0

@@ -0,0 +1,30 @@+Copyright Anton Kholomiov 2010++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Anton Kholomiov nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,3 @@+#!/usr/bin/env runhaskell+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,31 @@+Name:            data-fix+Version:         0.0.1+Cabal-Version:   >= 1.6+License:         BSD3+License-file:    LICENSE+Author:          Anton Kholomiov+Maintainer:      <anton.kholomiov@gmail.com>+Category:        Data+Synopsis:        Fixpoint data types+Build-Type:      Simple+Description:     +  Fixpoint types and recursion schemes. If you define your AST as+  fixpoint type, you get fold and unfold operations for free.++Stability:       Experimental++Homepage:        https://github.com/anton-k/data-fix+Bug-Reports:     https://github.com/anton-k/data-fix/issues++Source-repository head+    Type: git+    Location: https://github.com/anton-k/data-fix++Library+  Build-depends: base >= 4, base < 5+  Hs-source-dirs: src/++  ghc-options: -Wall++  Exposed-modules: +      Data.Fix

@@ -0,0 +1,106 @@+{-# Language +        FlexibleContexts, +        UndecidableInstances,+        TypeSynonymInstances #-}+-- | Fix-point type. It allows to define generic recurion schemes.+--+-- > Fix f = f (Fix f)+--+-- Type @f@ should be a 'Functor' if you want to use+-- simple recursion schemes or 'Traversable' if you want to+-- use monadic recursion schemes. This style allows you to express+-- recursive functions in non-recursive manner. +-- You can imagine that a non-recursive function +-- holds values of the previous iteration.+--+-- Little example:+--+-- > type List a = Fix (L a)+-- >+-- > data L a b = Nil | Cons a b+-- >+-- > instance Functor (L a) where+-- >    fmap f x = case x of+-- >        Nil      -> Nil+-- >        Cons a b -> Cons a (f b)+-- > +-- > length :: List a -> Int+-- > length = cata $ \x -> case x of+-- >    Nil      -> 0+-- >    Cons _ n -> n + 1+-- >+-- > sum :: Num a => List a -> a+-- > sum = cata $ \x -> case x of+-- >    Nil      -> 0+-- >    Cons a s -> a + s++module Data.Fix (+    Fix(..)+    -- * Simple recursion+    -- | Type @f@ should be a 'Functor'. They transform +    -- non-recursive functions to recursive ones. +    , cata+    , ana+    , hylo+    , (~>)+    -- * Monadic recursion+    -- | Type @f@ should be a 'Traversable'.+    , cataM+    , anaM+    , hyloM+    ) +where++import Control.Applicative+import Data.Traversable++-- | A fix-point type. +newtype Fix f = Fix { unFix :: f (Fix f) }++-- standard instances ++instance Show (f (Fix f)) => Show (Fix f) where+    show x = "(" ++ show (unFix x) ++ ")"+  +instance Eq (f (Fix f)) => Eq (Fix f) where+    a == b = unFix a == unFix b+  +instance Ord (f (Fix f)) => Ord (Fix f) where+    a `compare` b = unFix a `compare` unFix b+++-- recursion++-- | Catamorphism or generic function fold. +cata :: Functor f => (f a -> a) -> (Fix f -> a)+cata f = f . fmap (cata f) . unFix++-- | Anamorphism or generic function unfold. +ana :: Functor f => (a -> f a) -> (a -> Fix f)+ana f = Fix . fmap (ana f) . f++-- | Hylomorphism is anamorphism followed by catamorphism.+hylo :: Functor f => (f b -> b) -> (a -> f a) -> (a -> b) +hylo phi psi = cata phi . ana psi++-- | Infix version of @hylo@.+(~>) :: Functor f => (a -> f a) -> (f b -> b) -> (a -> b) +psi ~> phi = phi . (fmap $ hylo phi psi) . psi++-- monadic recursion++-- | Monadic catamorphism.+cataM :: (Applicative m, Monad m, Traversable t) +    => (t a -> m a) -> Fix t -> m a+cataM f = (f =<< ) . traverse (cataM f) . unFix++-- | Monadic anamorphism.+anaM :: (Applicative m, Monad m, Traversable t)+    => (a -> m (t a)) -> (a -> m (Fix t))+anaM f = fmap Fix . (traverse (anaM f) =<<) . f +   +-- | Monadic hylomorphism.+hyloM :: (Applicative m, Monad m, Traversable t)+    => (t b -> m b) -> (a -> m (t a)) -> (a -> m b)+hyloM phi psi = (cataM phi =<< ) . anaM psi+