packages feed

weave-core (empty) → 0.1.0.0

raw patch · 7 files changed

+225/−0 lines, 7 filesdep +basedep +some

Dependencies added: base, some

Files

+ CHANGELOG.md view
@@ -0,0 +1,5 @@+# Revision history for weave
+
+## 0.1.0.0 -- YYYY-mm-dd
+
+* First version. Released on an unsuspecting world.
+ LICENSE view
@@ -0,0 +1,29 @@+Copyright (c) 2025, Li-yao Xia
+
+
+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 the copyright holder nor the names of its
+      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
+HOLDER 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.
+ src/Weave/Endless.hs view
@@ -0,0 +1,60 @@+{-# LANGUAGE GADTs, PatternSynonyms #-}+-- | Endless weaves enable (almost) maximally lazy breadth-first unfolds:+-- an @unfoldM@ using this module, when specialized to the @Identity@ functor,+-- has the same lazy behavior as a pure @unfold@.+--+-- The main drawback is that the resulting unfolds are slow, with quadratic complexity.+module Weave.Endless+  ( Weave+  , Weaving+  , weft+  , mesh+  ) where++import Data.Some.Newtype (Some(Some))++{-+-- The implementation I really wanted+-- (not possible because lazy patterns are not supported on existential types):++data Weave m a where+  Weft :: m (Weave m b) -> (b -> a) -> Weave m a++instance Functor (Weave m) where+  fmap f ~(Weft u g) = Weft u (f . g)++instance Applicative m => Applicative (Weave m) where+  pure x = Weft (pure (pure ())) (\_ -> x)+  liftA2 f ~(Weft u g) ~(Weft v h) = Weft ((liftA2 . liftA2) (,) u v) (\ ~(x, y) -> f (g x) (h y))++weft :: m (Weave m a) -> Weave m a+weft u = Weft u id++mesh :: Monad m => Weave m a -> m a+mesh (Weft u f) = f <$> (u >>= mesh)+-}++-- | If you use this, you probably also want to import 'Data.Some.Newtype.Some' from the library @some@.+data Weaving m a b where+  Weft :: m (Weave m b) -> (b -> a) -> Weaving m a b++-- | Endless weaves.+--+-- The 'Applicative' operation @('liftA2')@ combines weaves level-wise.+newtype Weave m a = MkWeave (Some (Weaving m a))++instance Functor (Weave m) where+  fmap f (MkWeave (Some ~(Weft u g))) = MkWeave (Some (Weft u (f . g)))++instance Applicative m => Applicative (Weave m) where+  pure x = MkWeave (Some (Weft (pure (pure ())) (\_ -> x)))+  liftA2 f (MkWeave (Some ~(Weft u g))) (MkWeave (Some ~(Weft v h)))+    = MkWeave (Some (Weft ((liftA2 . liftA2) (,) u v) (\ ~(x, y) -> f (g x) (h y))))++-- | A weft is one level of 'Weave'. It is a computation which returns the remaining levels.+weft :: m (Weave m a) -> Weave m a+weft u = MkWeave (Some (Weft u id))++-- | Run all the wefts in a 'Weave' sequentially.+mesh :: Monad m => Weave m a -> m a+mesh (MkWeave (Some (Weft u f))) = f <$> (u >>= mesh)
+ src/Weave/Lazy.hs view
@@ -0,0 +1,33 @@+{-# LANGUAGE GADTs #-}+-- | Lazy weaves enable linear-time implementations of breadth-first unfolds.+module Weave.Lazy+  ( Weave(..)+  , weft+  , mesh+  ) where++-- | Lazy weaves.+--+-- The 'Applicative' operation @('liftA2')@ combines weaves level-wise.+data Weave m a where+  Pure :: a -> Weave m a+  Weft :: m (Weave m b) -> (b -> a) -> Weave m a++instance Functor (Weave m) where+  fmap f (Pure x) = Pure (f x)+  fmap f (Weft u g) = Weft u (f . g)++instance Applicative m => Applicative (Weave m) where+  pure = Pure+  liftA2 f (Pure x) u = fmap (f x) u+  liftA2 f (Weft u g) (Pure y) = Weft u (\x -> f (g x) y)+  liftA2 f (Weft u g) (Weft v h) = Weft (liftA2 (liftA2 (,)) u v) (\ ~(x, y) -> f (g x) (h y))++-- | A weft is one level of 'Weave'. It is a computation which returns the remaining levels.+weft :: m (Weave m a) -> Weave m a+weft u = Weft u id++-- | Run all the wefts in a 'Weave' sequentially.+mesh :: Monad m => Weave m a -> m a+mesh (Pure x) = pure x+mesh (Weft u f) = f <$> (u >>= mesh)
+ src/Weave/Oblivious.hs view
@@ -0,0 +1,28 @@+-- | Oblivious weaves forget the tree they are morally unfolding, saving energy.
+-- Like "Weave.Lazy", oblivious weaves enable linear-time breadth-first unfolds,
+-- but unlike "Weave.Lazy", they don't produce a tree.
+module Weave.Oblivious where
+
+-- | Oblivious weaves.
+--
+-- The 'Semigroup' operation @('<>')@ combines weaves level-wise.
+data Weave m
+  = End
+  | Weft (m (Weave m))
+
+instance Applicative m => Semigroup (Weave m) where
+  End <> u = u
+  u <> End = u
+  Weft u <> Weft v = Weft (liftA2 (<>) u v)
+
+instance Applicative m => Monoid (Weave m) where
+  mempty = End
+
+-- | A weft is one level of 'Weave'. It is a computation which returns the remaining levels.
+weft :: m (Weave m) -> Weave m
+weft = Weft
+
+-- | Run all the wefts in a 'Weave' sequentially.
+mesh_ :: Monad m => Weave m -> m ()
+mesh_ End = pure ()
+mesh_ (Weft u) = u >>= mesh_
+ src/Weave/Strict.hs view
@@ -0,0 +1,37 @@+{-# LANGUAGE GADTs #-}+-- | Strict weaves are the naive implementation of the idea "what if we generalized @zip@ to free monads?"+--+-- The resulting breadth-first unfold take quadratic time, which is slow.+--+-- The main reason for making this available is to compare it with the other variants.+module Weave.Strict+  ( Weave(..)+  , weft+  , mesh+  ) where++-- | Strict weaves.+--+-- The 'Applicative' operation @('liftA2')@ combines weaves level-wise.+data Weave m a where+  Pure :: a -> Weave m a+  Weft :: m (Weave m a) -> Weave m a++instance Functor m => Functor (Weave m) where+  fmap f (Pure x) = Pure (f x)+  fmap f (Weft u) = Weft ((fmap . fmap) f u)++instance Applicative m => Applicative (Weave m) where+  pure = Pure+  liftA2 f (Pure x) u = fmap (f x) u+  liftA2 f (Weft u) (Pure y) = Weft ((fmap . fmap) (\x -> f x y) u)+  liftA2 f (Weft u) (Weft v) = Weft ((liftA2 . liftA2) f u v)++-- | A weft is one level of 'Weave'. It is a computation which returns the remaining levels.+weft :: m (Weave m a) -> Weave m a+weft = Weft++-- | Run all the wefts in a 'Weave' sequentially.+mesh :: Monad m => Weave m a -> m a+mesh (Pure x) = pure x+mesh (Weft u) = u >>= mesh
+ weave-core.cabal view
@@ -0,0 +1,33 @@+cabal-version:      3.0
+name:               weave-core
+version:            0.1.0.0
+synopsis: Core definitions for weave
+description:
+  The four variants of @Weave@, a control structure for defining
+  /breadth-first unfolds/ compositionally.
+  .
+  See <https://hackage.haskell.org/package/weave weave> for more information.
+license:            BSD-3-Clause
+license-file:       LICENSE
+author:             Li-yao Xia
+maintainer:         lysxia@gmail.com
+homepage:           https://gitlab.com/lysxia/weave
+category:           Control
+build-type:         Simple
+extra-doc-files:    CHANGELOG.md
+
+common warnings
+    ghc-options: -Wall
+
+library
+    import:           warnings
+    exposed-modules:
+        Weave.Endless
+        Weave.Lazy
+        Weave.Oblivious
+        Weave.Strict
+    build-depends:
+        some < 1.1,
+        base >= 4 && < 5
+    hs-source-dirs:   src
+    default-language: Haskell2010