heftia 0.4.0.0 → 0.5.0.0

raw patch · 10 files changed

+508/−175 lines, 10 filesdep −freer-simpledep ~data-effectsPVP ok

version bump matches the API change (PVP)

Dependencies removed: freer-simple

Dependency ranges changed: data-effects

API changes (from Hackage documentation)

Files

• ChangeLog.md +5/−0
• README.md +261/−103
• heftia.cabal +10/−13
• src/Control/Monad/Hefty.hs +52/−23
• src/Control/Monad/Hefty/Interpret.hs +54/−18
• src/Control/Monad/Hefty/Transform.hs +27/−0
• src/Data/Effect/OpenUnion/Internal.hs +13/−2
• src/Data/Effect/OpenUnion/Internal/FO.hs +5/−8
• src/Data/Effect/OpenUnion/Internal/HO.hs +5/−8
• src/Data/FTCQueue.hs +76/−0

@@ -27,3 +27,8 @@         * The interface is largely the same as before, but names have been changed throughout. * Dropped support for GHC 9.2.8, now supporting GHC 9.4.1 and later. * Added detailed explanations on how to use Heftia and its semantics to the Haddock documentation of the `Control.Monad.Hefty` module.++## 0.5.0.0 -- 2024-11-03++* Fixed a bug in the lookup of keyed effects.+* Added missing functions such as `key`, `keyH`, `raiseAll`, and `raiseAllH`.

@@ -1,19 +1,15 @@-# Heftia: higher-order effects done right for Haskell+# Heftia: higher-order algebraic effects done right  [![Hackage](https://img.shields.io/hackage/v/heftia.svg?logo=haskell&label=heftia)](https://hackage.haskell.org/package/heftia) [![Hackage](https://img.shields.io/hackage/v/heftia-effects.svg?logo=haskell&label=heftia-effects)](https://hackage.haskell.org/package/heftia-effects)+[![Stackage](https://www.stackage.org/package/heftia-effects/badge/nightly?label=Stackage)](https://www.stackage.org/package/heftia-effects)+[![Build status](https://img.shields.io/github/actions/workflow/status/sayo-hs/heftia/haskell.yml?branch=develop)](https://github.com/sayo-hs/heftia/actions) -Heftia is an extensible effects library that generalizes "Algebraic Effects and Handlers" to higher-order effects, providing users with maximum flexibility and delivering standard and reasonable speed.+Heftia is an extensible effects library for Haskell that generalizes "Algebraic Effects and Handlers" to higher-order effects, providing users with maximum flexibility and delivering standard and reasonable speed. In its generalization, the focus is on ensuring predictable results based on simple, consistent semantics, while preserving soundness. -Please refer to the [Haddock documentation](https://hackage.haskell.org/package/heftia-0.4.0.0/docs/Control-Monad-Hefty.html) for usage and semantics.-For information on performance, please refer to [performance.md](https://github.com/sayo-hs/heftia/blob/v0.4.0/benchmark/performance.md).--The library allows the following effects with well-defined semantics:--* Coroutines-* Non-deterministic computations-* `MonadUnliftIO`+Please refer to the [Haddock documentation](https://hackage.haskell.org/package/heftia-0.5.0.0/docs/Control-Monad-Hefty.html) for usage and semantics.+For information on performance, please refer to [performance.md](https://github.com/sayo-hs/heftia/blob/v0.5.0/benchmark/performance.md).  This library is inspired by the paper: * Casper Bach Poulsen and Cas van der Rest. 2023. Hefty Algebras: Modular@@ -24,12 +20,87 @@  Heftia's data structure is an extension of the Freer monad, designed to be theoretically straightforward by eliminating ad-hoc elements. +## Why choose this library over others?+This library is based on algebraic effects. Currently, **none of the practical effect libraries other than this one are "algebraic."** So, why is being *algebraic* important?++For example, algebraic effects are essential for managing coroutines, generators, streaming, concurrency, non-deterministic computations, and more in a highly elegant and concise manner.++Algebraic effects provide a consistent and predictable framework for handling side effects, enhancing modularity and flexibility in your code.+Research in cutting-edge languages like [Koka](https://koka-lang.github.io/koka/doc/index.html), [Eff lang](https://www.eff-lang.org/), and [OCaml 5](https://ocaml.org/manual/effects.html) is advancing the understanding and implementation of algebraic effects, establishing them as **the programming paradigm of the future**.++Heftia extends this by supporting higher-order algebraic effects, allowing for more expressive and modular effect management.+This leads to more maintainable and extensible applications compared to non-algebraic effect libraries, positioning Heftia at **the forefront of modern effect handling techniques**.++Furthermore, **Heftia is functionally a superset of other effect libraries**, especially those based on `ReaderT` over `IO`.+In other words, anything that is possible with other libraries is also possible with this library.+This is because Heftia supports `MonadUnliftIO` in the form of higher-order effects.++**Heftia should be a good substitute for `mtl`, `polysemy`, `fused-effects`, and `freer-simple`.**+Additionally, if performance is not a top priority, it should also be a good alternative for `effectful`.+If performance is particularly important, [`effectful`](https://github.com/haskell-effectful/effectful) would be the best alternative to this library.++## Key Features++* **Correct Semantics for Higher-Order Effects & Continuations**++    This library provides the following features simultaneously, which existing libraries could not support together:++    * Delimited continuations (algebraic effects)+        * Coroutines (non-scoped resumptions)+        * Coroutine-based, composable, and resumable concurrent streams+        * Non-deterministic computations++    * Higher-order effects+        * [`MonadUnliftIO`](https://hackage.haskell.org/package/unliftio)+            * to prevent resource leaks due to runtime exceptions+            * [heftia-effects/Example/UnliftIO/Main.hs](https://github.com/sayo-hs/heftia/blob/v0.5.0/heftia-effects/Example/UnliftIO/Main.hs)+            * [heftia-effects/Example/Stream/Main.hs](https://github.com/sayo-hs/heftia/blob/v0.5.0/heftia-effects/Example/Stream/Main.hs)+        * [`Provider`](https://hackage.haskell.org/package/effectful-core-2.5.0.0/docs/Effectful-Provider.html) a.k.a. [`Scoped`](https://hackage.haskell.org/package/polysemy-1.9.2.0/docs/Polysemy-Scoped.html)+            * to prevent [resource handles from leaking out of scopes](https://h2.jaguarpaw.co.uk/posts/bluefin-prevents-handles-leaking/)+            * [Control.Monad.Hefty.Concurrent.Subprocess](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-Concurrent-Subprocess.html)+            * [heftia-effects/Example/Subprocess/Main.hs](https://github.com/sayo-hs/heftia/blob/v0.5.0/heftia-effects/Example/Subprocess/Main.hs)+            * [heftia-effects/Example/FileSystemProvider/Main.hs](https://github.com/sayo-hs/heftia/blob/v0.5.0/heftia-effects/Example/FileSystemProvider/Main.hs)+        * [Applicative-style Parallelism](https://medium.com/@PerrottaFrancisco/learning-cats-effects-parallel-execution-f617f883e390)+            * like `cats-effect` in Scala+            * [Data.Effect.Concurrent.Parallel](https://hackage.haskell.org/package/data-effects-0.3.0.1/docs/Data-Effect-Concurrent-Parallel.html)+            * [Control.Monad.Hefty.Concurrent.Parallel](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-Concurrent-Parallel.html)+            * [heftia-effects/test/Test/Concurrent.hs](https://github.com/sayo-hs/heftia/blob/v0.5.0/heftia-effects/test/Test/Concurrent.hs)++    All of these interact through a simple, consistent, and predictable semantics based on algebraic effects.++* **Easy and Concise Implementation for Custom Effect Interpreters**++    As you can see from the implementations of basic effect interpreters such as [State](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/src/Control.Monad.Hefty.State.html#runState), [Throw/Catch](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/src/Control.Monad.Hefty.Except.html#runThrow), [Writer](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/src/Control.Monad.Hefty.Writer.html#runTell), [NonDet](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/src/Control.Monad.Hefty.NonDet.html#runNonDet), and [Coroutine](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/src/Control.Monad.Hefty.Coroutine.html#runCoroutine), they can be implemented in just a few lines, or even a single line. Even for effects like NonDet and Coroutine, which involve continuations and might seem difficult to implement at first glance, this is exactly how simple it can be. This is the power of algebraic effects. Users can quickly define experimental and innovative custom effects using continuations.++* **Standard and Reasonable Performance**++    It operates at a speed positioned roughly in the middle between faster libraries (like `effectful` or `eveff`) and relatively slower ones (like `polysemy` or `fused-effects`): [performance.md](https://github.com/sayo-hs/heftia/blob/v0.5.0/benchmark/performance.md).++* **Purity**++    * Does not depend on the IO monad and can use any monad as the base monad.+    * Semantics are isolated from the IO monad, meaning that aspects like asynchronous exceptions and threads do not affect the behavior of effects.+    * The constructors of the `Eff` monad are [exposed](https://hackage.haskell.org/package/heftia-0.5.0.0/docs/Control-Monad-Hefty.html#t:Eff), and users can manipulate them directly without any safety concerns. Still, the semantics remain intact.+    * These are in contrast to libraries like `effectful` and `eff`, making this library more **Haskell-ish and purely functional**.++## Downsides++This library has notable semantic differences, particularly compared to libraries like `effectful`, `polysemy`, and `fused-effects`.+The semantics of this library are almost equivalent to those of `freer-simple` and are also similar to Alexis King's `eff` library.+This type of semantics is often referred to as *continuation-based semantics*.+Additionally, unlike recent libraries such as `effectful`, which have an IO-fused effect system, the semantics of this library are separated from IO.+Due to these differences, people who are already familiar with the semantics of other major libraries may find it challenging to transition to this library due to the mental model differences.++For those who have not used an extensible effects library in Haskell before, this should not be a problem.+Particularly, if you are already somewhat familiar with the semantics of algebraic effects through languages like `koka` or `eff-lang`,+you likely already have the mental model needed for this library, and everything should go smoothly.+ ## Status  This library is currently in the beta stage. There may be significant changes and potential bugs. -**We are looking forward to your feedback!**+**I am looking forward to your feedback!**  ## Getting Started 1.@@ -73,113 +144,189 @@         TemplateHaskell,         PartialTypeSignatures,         AllowAmbiguousTypes--    ghc-options: ... -fplugin GHC.TypeLits.KnownNat.Solver ... ``` -The supported versions are GHC 9.4.1 and later.-This library has been tested with GHC 9.8.2 and 9.4.1.+If you encounter an error like the following, add the pragma: -## Getting Started+```haskell+{-# OPTIONS_GHC -fplugin GHC.TypeLits.KnownNat.Solver #-}+``` -## Example+to the header of your source file. -Compared to existing Effect System libraries in Haskell that handle higher-order effects, this-library's approach allows for a more effortless and flexible handling of higher-order effects. Here-are some examples:+    Could not deduce ‘GHC.TypeNats.KnownNat (1 GHC.TypeNats.+ ...)’ -### Extracting Multi-shot Delimited Continuations+The supported versions are GHC 9.4.1 and later.+This library has been tested with GHC 9.4.1, 9.6.6 and 9.8.2. -In handling higher-order effects, it's easy to work with **multi-shot delimited continuations**.-For more details, please refer to-the [example code](https://github.com/sayo-hs/heftia/blob/v0.4.0/heftia-effects/Example/Continuation/Main.hs).+## Example -### Two interpretations of the `censor` effect for Writer+### Coroutine-based Composable Concurrent Stream (since v0.5) -Let's consider the following Writer effectful program:+Below is an example of using concurrent streams (pipes). -```hs-hello :: (Tell String <: m, Monad m) => m ()-hello = do-    tell "Hello"-    tell " world!"+```haskell+{-# OPTIONS_GHC -fplugin GHC.TypeLits.KnownNat.Solver #-} -censorHello :: (Tell String <: m, WriterH String <<: m, Monad m) => m ()-censorHello =-    censor-        ( \s ->-            if s == "Hello" then-                "Goodbye"-            else if s == "Hello world!" then-                "Hello world!!"-            else-                s-        )-        hello-```+import Control.Monad.Hefty+import Control.Monad.Hefty.Concurrent.Stream+import Control.Monad.Hefty.Concurrent.Timer+import Control.Monad.Hefty.Except+import Control.Monad.Hefty.Unlift+import Control.Arrow ((>>>))+import Control.Monad (forever, void, when)+import Data.Foldable (for_)+import UnliftIO (bracket_) -For `censorHello`, should the final written string be `"Goodbye world!"` (Pre-applying behavior) ?-Or should it be `"Hello world!!"` (Post-applying behavior) ?-With Heftia, **you can freely choose either behavior depending on which higher-order effect interpreter (which we call an elaborator) you use**.+-- | Generates a sequence of 1, 2, 3, 4 at 0.5-second intervals.+produce :: (Output Int <| ef, Timer <| ef) => Eff '[] ef ()+produce = void . runThrow @() $+    for_ [1 ..] \(i :: Int) -> do+        when (i == 5) $ throw ()+        output i+        sleep 0.5 -```hs-main :: IO ()-main = runEff do-    (sPre, _) <--        runTell-            . runWriterHPre @String-            $ censorHello+-- | Receives the sequence at 0.5-second intervals and prints it.+consume :: (Input Int <| ef, Timer <| ef, IO <| ef) => Eff eh ef ()+consume = forever do+    liftIO . print =<< input @Int+    sleep 0.5 -    (sPost, _) <--        runTell-            . runWriterHPost @String-            $ censorHello+-- | Transforms by receiving the sequence as input at 0.5-second intervals,+--   adds 100, and outputs it.+plus100 :: (Input Int <| ef, Output Int <| ef, Timer <| ef, IO <| ef) => Eff eh ef ()+plus100 = forever do+    i <- input @Int+    let o = i + 100+    liftIO $ putStrLn $ "Transform " <> show i <> " to " <> show o+    output o+    sleep 0.5 -    liftIO $ putStrLn $ "Pre-applying: " <> sPre-    liftIO $ putStrLn $ "Post-applying: " <> sPost+main :: IO ()+main = runUnliftIO . runTimerIO $ do+    let produceWithBracket =+            bracket_+                (liftIO $ putStrLn "Start")+                (liftIO $ putStrLn "End")+                (raiseAllH produce)++    runMachineryIO_ $+        Unit @() @Int do+            produceWithBracket+            produceWithBracket+            >>> Unit @Int @Int plus100+            >>> Unit @Int @() consume ``` -Using the `elabWriterPre` elaborator, you'll get "Goodbye world!", whereas with the `elabWriterPost` elaborator, you'll get "Hello world!!". ```-Pre-applying: Goodbye world!-Post-applying: Hello world!!+>>> main+Start+Transform 1 to 101+101+Transform 2 to 102+102+Transform 3 to 103+103+Transform 4 to 104+104+End+Start+Transform 1 to 101+101+Transform 2 to 102+102+Transform 3 to 103+103+Transform 4 to 104+104+End ``` -For more details, please refer to the [complete code](https://github.com/sayo-hs/heftia/blob/v0.4.0/heftia-effects/Example/Writer/Main.hs) and the [implementation of the elaborator](https://github.com/sayo-hs/heftia/blob/v0.4.0/heftia-effects/src/Control/Effect/Interpreter/Heftia/Writer.hs).+* Each function (machine unit) `produce`, `consume`, and `plus100` operates with input/output at 0.5-second intervals, but note that the composed stream also maintains operation intervals at 0.5 seconds (not 1.5 seconds!). This means that each unit operates concurrently based on threads. -### Semantics Zoo-To run the [SemanticsZoo example](https://github.com/sayo-hs/heftia/blob/v0.4.0/heftia-effects/Example/SemanticsZoo/Main.hs):-```console-$ git clone https://github.com/sayo-hs/heftia-$ cd heftia/heftia-effects-$ cabal run exe:SemanticsZoo-...-# State & Except-( evalState . runThrow . runCatch $ action ) = Right True-( runThrow . evalState . runCatch $ action ) = Right True+* `End` is displayed just after the first sequence ends and before the second sequence starts. This demonstrates that the `bracket_` function based on `MonadUnliftIO` for safe resource release works in such a way that resources are released immediately at the correct timing—even if the stream is still in progress—rather than waiting until the entire stream (including the second sequence) has completed. Existing stream libraries like [`pipes`](https://hackage.haskell.org/package/pipes) and [`conduit`](https://hackage.haskell.org/package/conduit) have the issue that immediate resource release like this is not possible. This problem was first addressed by the effect system library [`bluefin`](https://github.com/tomjaguarpaw/bluefin). For more details, please refer to [Bluefin streams finalize promptly](https://h2.jaguarpaw.co.uk/posts/bluefin-streams-finalize-promptly/). -# NonDet & Except-( runNonDet . runThrow . runCatch . runChooseH $ action1 ) = [Right True,Right False]-( runThrow . runNonDet . runCatch . runChooseH $ action1 ) = Right [True,False]-( runNonDet . runThrow . runCatch . runChooseH $ action2 ) = [Right False,Right True]-( runThrow . runNonDet . runCatch . runChooseH $ action2 ) = Right [False,True]+The complete code example can be found at [heftia-effects/Example/Stream/Main.hs](https://github.com/sayo-hs/heftia/blob/v0.5.0/heftia-effects/Example/Stream/Main.hs). -# NonDet & Writer-( runNonDet . runTell . runWriterH . runChooseH $ action ) = [(3,(3,True)),(4,(4,False))]-( runTell . runNonDet . runWriterH . runChooseH $ action ) = (6,[(3,True),(4,False)])+### Aggregating File Sizes Using Non-Deterministic Computation -# https://github.com/hasura/eff/issues/12-interpret SomeEff then runCatch : ( runThrow . runCatch . runSomeEff $ action ) = Right "caught"-runCatch then interpret SomeEff : ( runThrow . runSomeEff . runCatch $ action ) = Left "not caught"+The following is an extract of the main parts from an example of non-deterministic computation. For the full code, please refer to [heftia-effects/Example/NonDet/Main.hs](https://github.com/sayo-hs/heftia/blob/v0.5.0/heftia-effects/Example/NonDet/Main.hs). -[Note] All other permutations will cause type errors.-$+```haskell+-- | Aggregate the sizes of all files under the given path+totalFileSize+    :: (Choose <| ef, Empty <| ef, FileSystem <| ef, Throw NotADir <| ef, IO <| ef)+    => FilePath+    -> Eff '[] ef (Sum Integer)+totalFileSize path = do+    entities :: [FilePath] <- listDirectory path & joinEither++    -- Non-deterministically *pick* one item from the list+    entity :: FilePath <- choice entities++    let path' = path </> entity++    liftIO $ putStrLn $ "Found " <> path'++    getFileSize path' >>= \case+        Right size -> do+            liftIO $ putStrLn $ " ... " <> show size <> " bytes"+            pure $ Sum size+        Left NotAFile -> do+            totalFileSize path'++main :: IO ()+main = runEff+    . runThrowIO @EntryNotFound+    . runThrowIO @NotADir+    . runDummyFS exampleRoot+    $ do+        total <- runNonDetMonoid pure (totalFileSize ".")+        liftIO $ print total++-- | Effect for file system operations+data FileSystem a where+    ListDirectory :: FilePath -> FileSystem (Either NotADir [FilePath])+    GetFileSize :: FilePath -> FileSystem (Either NotAFile Integer)++{- |+Interpreter for the FileSystem effect that virtualizes the file system in memory+based on a given FSTree, instead of performing actual IO.+-}+runDummyFS+    :: (Throw EntryNotFound <| ef, Throw NotADir <| ef)+    => FSTree+    -> Eff eh (FileSystem ': ef) ~> Eff eh ef+runDummyFS root = interpret \case+    ListDirectory path ->+        lookupFS path root <&> \case+            Dir entries -> Right $ Map.keys entries+            File _ -> Left NotADir+    GetFileSize path ->+        lookupFS path root <&> \case+            File size -> Right size+            Dir _ -> Left NotAFile ``` +```+>>> main+Found ./README.md+ ... 4000 bytes+Found ./src+Found ./src/Bar.hs+ ... 1000 bytes+Found ./src/Foo.hs+ ... 2000 bytes+Found ./test+Found ./test/Baz.hs+ ... 3000 bytes+Sum {getSum = 10000}+```+ ## Documentation-A detailed explanation of usage and semantics is available in [Haddock](https://hackage.haskell.org/package/heftia-0.4.0.0/docs/Control-Monad-Hefty.html).-The example codes are located in the [heftia-effects/Example/](https://github.com/sayo-hs/heftia/tree/v0.4.0/heftia-effects/Example) directory.+A detailed explanation of usage and semantics is available in [Haddock](https://hackage.haskell.org/package/heftia-0.5.0.0/docs/Control-Monad-Hefty.html).+The example codes are located in the [heftia-effects/Example/](https://github.com/sayo-hs/heftia/tree/v0.5.0/heftia-effects/Example) directory. Also, the following *HeftWorld* example (outdated): https://github.com/sayo-hs/HeftWorld  About the internal *elaboration* mechanism: https://sayo-hs.github.io/jekyll/update/2024/09/04/how-the-heftia-extensible-effects-library-works.html@@ -206,20 +353,21 @@ | `freer-simple`      | No                   | Multi-shot             | Yes           | Yes                               | Yes                      | Algebraic Effects                | | `polysemy`          | Yes                  | No                     | Yes           | Yes                               | Yes                      | Weaving-based (functorial state) | | `effectful`         | Yes                  | No                     | Yes           | No (based on the `IO` monad)      | Yes                      | IO-fused                         |+| `bluefin`           | Yes                  | No                     | Yes           | No (based on the `IO` monad)      | Yes                      | IO-fused                         | | `eff`               | Yes                  | Multi-shot             | Yes           | No (based on the `IO` monad)      | Yes                      | Algebraic Effects & IO-fused [^6]| | `speff`             | Yes                  | Multi-shot (restriction: [^4]) | Yes   | No (based on the `IO` monad)      | Yes                      | Algebraic Effects & IO-fused     | | `in-other-words`    | Yes                  | Multi-shot?            | Yes           | Yes                               | No?                      | Carrier dependent                | | `mtl`               | Yes                  | Multi-shot (`ContT`)   | Yes           | Yes                               | No                       | Carrier dependent                | | `fused-effects`     | Yes                  | No?                    | Yes           | Yes                               | No                       | Carrier dependent & Weaving-based (functorial state) | | Koka-lang           | No                   | Multi-shot             | Yes           | No (language built-in)            | Yes                      | Algebraic Effects                |-| OCaml-lang 5        | ?                    | One-shot               | No [^3]       | No (language built-in)            | ?                        | Algebraic Effects?               |+| Eff-lang            | No                   | Multi-shot             | Yes           | No (language built-in)            | Yes                      | Algebraic Effects                |+| OCaml-lang 5        | ?                    | One-shot               | No [^3]       | No (language built-in)            | ?                        | Algebraic Effects                |  [^3]: Effects do not appear in the type signature and can potentially cause unhandled errors at runtime [^4]: Scoped Resumption only. e.g. Coroutines are not supported.-[^5]: https://github.com/sayo-hs/heftia/issues/12 [^6]: https://github.com/hasura/eff/issues/12 -Heftia can simply be described as a higher-order version of freer-simple.+Heftia can simply be described as a higher-order version of `freer-simple`. This is indeed true in terms of its internal mechanisms as well.  Additionally, this library provides a consistent algebraic effects semantics that is independent of carriers and effects.@@ -237,45 +385,53 @@ Overall, the performance of this library is positioned roughly in the middle between the fast (`effectful`, `eveff`, etc.) and slow (`polysemy`, `fused-effects`, etc.) libraries, and can be considered average. In all benchmarks, the speed is nearly equivalent to `freer-simple`, only slightly slower. -For more details, please refer to [performance.md](https://github.com/sayo-hs/heftia/blob/v0.4.0/benchmark/performance.md).+For more details, please refer to [performance.md](https://github.com/sayo-hs/heftia/blob/v0.5.0/benchmark/performance.md). -### Compatibility with other libraries+### Interoperability with other libraries -#### About mtl+#### About `mtl` * Since the representation of effectful programs in Heftia is simply a monad (`Eff`), it can be used as the base monad for transformers.     This means you can stack any transformer on top of it.  * The `Eff` monad is an instance of `MonadIO`, `MonadError`, `MonadRWS`, `MonadUnliftIO`, `Alternative`, etc., and these behave as the senders for the embedded `IO` or the effect GADTs defined in [data-effects](https://github.com/sayo-hs/data-effects). +#### About `effectful`++* In Heftia, since any monad can be used as the base monad of `Eff`, by setting the `Eff` monad from `effectful` as the base monad of Heftia, you can stack any effect in Heftia on top of `effectful`. In other words, the `Eff` of `Heftia` itself can be used like a monad transformer. This is not limited to `effectful`.++* By using `Control.Monad.Hefty.Unlift.runUnliftIO` instead of `Control.Monad.Hefty.runEff`, you can inherit and use the `MonadUnliftIO` functionality of `effectful`'s `Eff` as a higher-order `UnliftIO` effect within Heftia.+ #### Representation of effects * Heftia relies on [data-effects](https://hackage.haskell.org/package/data-effects) for the definitions of standard effects such as `Reader`, `Writer`, and `State`.  * It is generally recommended to use effects defined with automatic derivation provided by [data-effects-th](https://hackage.haskell.org/package/data-effects-th). -* The representation of first-order effects is compatible with freer-simple.-    Therefore, effects defined for freer-simple can be used as is in this library.+* The representation of first-order effects is compatible with `freer-simple`.+    Therefore, effects defined for `freer-simple` can be used as is in this library.     However, to avoid confusion between redundantly defined effects,     it is recommended to use the effects defined in `data-effects`. -* GADTs for higher-order effects are formally similar to Polysemy and fused-effects,+* GADTs for higher-order effects are formally similar to `polysemy` and `fused-effects`,     but they need to be instances of the [`HFunctor`](https://hackage.haskell.org/package/compdata-0.13.1/docs/Data-Comp-Multi-HFunctor.html#t:HFunctor) type class.     While it's not impossible to manually derive `HFunctor` for effect types based on these libraries and use them,     it's inconvenient, so it's better to use `data-effects`.-    Also, it is not compatible with Effectful and eff.+    Also, it is not compatible with `effectful` and `eff`.  ## Future Plans+* Increase effects and nurture the ecosystem+    * file system, POSIX, and so on...+* Write practical software using Heftia * Support for Applicative effects-* Completing lacking definitions such as-    * interpreters for the `Accum` and others effects+* (Support for [Linear](https://hackage.haskell.org/package/linear-base) effects?)  ## License-The license is MPL 2.0. Please refer to the [NOTICE](https://github.com/sayo-hs/heftia/blob/v0.4.0/NOTICE).+The license is MPL 2.0. Please refer to the [NOTICE](https://github.com/sayo-hs/heftia/blob/v0.5.0/NOTICE). Additionally, the code from `freer-simple` has been modified and used internally within this library. Therefore, some modules are licensed under both `MPL-2.0 AND BSD-3-Clause`. For details on licenses and copyrights, please refer to the module's Haddock documentation.  ## Your contributions are welcome!-Please see [CONTRIBUTING.md](https://github.com/sayo-hs/heftia/blob/v0.4.0/CONTRIBUTING.md).+Please see [CONTRIBUTING.md](https://github.com/sayo-hs/heftia/blob/v0.5.0/CONTRIBUTING.md).  ## Acknowledgements, citations, and related work The following is a non-exhaustive list of people and works that have had a significant impact, directly or indirectly, on Heftia’s design and implementation:@@ -286,6 +442,7 @@ - Sandy Maguire and other contributors — [`polysemy`][gh:polysemy] - Alexis King and other contributors — [`freer-simple`][gh:freer-simple], [`eff`][gh:eff] - Casper Bach Poulsen and Cas van der Rest — [Hefty Algebras: Modular Elaboration of Higher-Order Algebraic Effects][casper:hefty]+- Tom Ellis — [Bluefin streams finalize promptly][tom:bluefin-streams]  [gh:fused-effects]: https://github.com/fused-effects/fused-effects [gh:polysemy]: https://github.com/polysemy-research/polysemy@@ -294,3 +451,4 @@ [casper:hefty]: https://dl.acm.org/doi/10.1145/3571255 [gh:freer-simple]: https://github.com/lexi-lambda/freer-simple [gh:eff]: https://github.com/lexi-lambda/eff+[tom:bluefin-streams]: https://h2.jaguarpaw.co.uk/posts/bluefin-streams-finalize-promptly/

@@ -1,23 +1,19 @@ cabal-version:      2.4 name:               heftia-version:            0.4.0.0+version:            0.5.0.0  -- A short (one-line) description of the package.-synopsis: higher-order effects done right+synopsis: higher-order algebraic effects done right  -- A longer description of the package. description:+    This is the core package for [heftia-effects](https://hackage.haskell.org/package/heftia-effects).+    .     Heftia is an extensible effects library that generalizes "Algebraic Effects and Handlers" to higher-order effects, providing users with maximum flexibility and delivering standard and reasonable speed.     In its generalization, the focus is on ensuring predictable results based on simple, consistent semantics, while preserving soundness.     .-    Please refer to the [Haddock documentation](https://hackage.haskell.org/package/heftia-0.4.0.0/docs/Control-Monad-Hefty.html) for usage and semantics.-    For information on performance, please refer to [performance.md](https://github.com/sayo-hs/heftia/blob/v0.4.0/benchmark/performance.md).-    .-    The library allows the following effects with well-defined semantics:-    .-    * Coroutines-    * Non-deterministic computations-    * `MonadUnliftIO`+    Please refer to the [Haddock documentation](https://hackage.haskell.org/package/heftia-0.5.0.0/docs/Control-Monad-Hefty.html) for usage and semantics.+    For information on performance, please refer to [performance.md](https://github.com/sayo-hs/heftia/blob/v0.5.0/benchmark/performance.md).     .     This library is inspired by the paper:     .@@ -52,12 +48,13 @@  tested-with:     GHC == 9.8.2+    GHC == 9.6.6     GHC == 9.4.1  source-repository head     type: git     location: https://github.com/sayo-hs/heftia-    tag: v0.4.0+    tag: v0.5.0     subdir: heftia  library@@ -72,6 +69,7 @@         Data.Effect.OpenUnion.Internal.FO         Data.Effect.OpenUnion.Internal.HO         Data.Effect.OpenUnion.Sum+        Data.FTCQueue      reexported-modules:         Data.Effect,@@ -93,8 +91,7 @@     -- other-extensions:     build-depends:         base                          >= 4.17 && < 4.21,-        data-effects                  ^>= 0.2,-        freer-simple                  ^>= 1.2.1.2,+        data-effects                  ^>= 0.3.0.1,         mtl                           >= 2.2.2 && < 2.4,         unliftio                      ^>= 0.2, 

@@ -20,6 +20,9 @@ named spans in a program.  @+{\-# LANGUAGE AllowAmbiguousTypes #-\}+{\-# LANGUAGE TemplateHaskell #-\}+ import "Control.Monad.Hefty" import Prelude hiding (log, span) @@ -77,10 +80,10 @@     Elaboration is generally performed by editing first-order (or higher-order) effectful operations within the computation held by the higher-order effect being elaborated.      @-    [runCatch](https://hackage.haskell.org/package/heftia-effects-0.4.0.0/docs/Control-Monad-Hefty-Except.html#v:runCatch) :: (@t'Data.Effect.Except.Throw'@ e t'Data.Effect.OpenUnion.<|' ef) => 'Eff' '[@t'Data.Effect.Except.Catch'@ e] ef t'Control.Effect.~>' 'Eff' '[] ef+    [runCatch](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-Except.html#v:runCatch) :: (@t'Data.Effect.Except.Throw'@ e t'Data.Effect.OpenUnion.<|' ef) => 'Eff' '[@t'Data.Effect.Except.Catch'@ e] ef t'Control.Effect.~>' 'Eff' '[] ef     runCatch = 'interpretH' elabCatch -    [elabCatch](https://hackage.haskell.org/package/heftia-effects-0.4.0.0/docs/Control-Monad-Hefty-Except.html#v:elabCatch) :: (@t'Data.Effect.Except.Throw'@ e t'Data.Effect.OpenUnion.<|' ef) => t'Data.Effect.Except.Catch' e t'Control.Monad.Hefty.~~>' 'Eff' '[] ef+    [elabCatch](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-Except.html#v:elabCatch) :: (@t'Data.Effect.Except.Throw'@ e t'Data.Effect.OpenUnion.<|' ef) => t'Data.Effect.Except.Catch' e t'Control.Monad.Hefty.~~>' 'Eff' '[] ef     elabCatch (@v'Data.Effect.Except.Catch'@ action hdl) = action & 'interposeWith' \\(@v'Data.Effect.Except.Throw'@ e) _ -> hdl e     @ @@ -103,10 +106,10 @@     By ignoring the continuation argument, it allows for global escapes like the 'Data.Effect.Except.Throw' effect.      @-    [runThrow](https://hackage.haskell.org/package/heftia-effects-0.4.0.0/docs/Control-Monad-Hefty-Except.html#v:runThrow) :: 'Eff' '[] (@t'Data.Effect.Except.Throw'@ e ': r) a -> 'Eff' '[] r ('Either' e a)+    [runThrow](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-Except.html#v:runThrow) :: 'Eff' '[] (@t'Data.Effect.Except.Throw'@ e ': r) a -> 'Eff' '[] r ('Either' e a)     runThrow = 'interpretBy' ('pure' '.' 'Right') handleThrow -    [handleThrow](https://hackage.haskell.org/package/heftia-effects-0.4.0.0/docs/Control-Monad-Hefty-Except.html#v:handleThrow) :: 'Interpreter' (@t'Data.Effect.Except.Throw'@ e) ('Eff' '[] r) ('Either' e a)+    [handleThrow](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-Except.html#v:handleThrow) :: 'Interpreter' (@t'Data.Effect.Except.Throw'@ e) ('Eff' '[] r) ('Either' e a)     handleThrow (@v'Data.Effect.Except.Throw'@ e) _ = 'pure' $ 'Left' e     @ @@ -115,7 +118,7 @@     By calling the continuation argument multiple times, it allows for non-deterministic computations like the "Data.Effect.NonDet" effect.      @-    [runNonDet](https://hackage.haskell.org/package/heftia-effects-0.4.0.0/docs/Control-Monad-Hefty-NonDet.html#v:runNonDet)+    [runNonDet](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-NonDet.html#v:runNonDet)         :: forall f ef a         . ('Alternative' f)         => 'Eff' '[] (@t'Data.Effect.NonDet.Choose'@ ': t'Data.Effect.NonDet.Empty' ': ef) a@@ -170,13 +173,13 @@     * Non-recursive continuational stateful interpretation functions like 'interpretWith' cannot be used unless the higher-order effects are empty:          @-        'interpretWith' :: e ~> Eff '[] ef => 'Eff' '[] (e ': ef) ~> 'Eff' '[] ef+        'interpretWith' :: e t'Control.Effect.~>' 'Eff' '[] ef -> 'Eff' '[] (e ': ef) t'Control.Effect.~>' 'Eff' '[] ef         @      * The @Rec@ versions can be used even when @eh@ is not empty.          @-        'interpretRecWith' :: e ~> 'Eff' eh (e ': ef) ~> 'Eff' eh ef+        'interpretRecWith' :: e t'Control.Effect.~>' 'Eff' eh ef -> 'Eff' eh (e ': ef) t'Control.Effect.~>' 'Eff' eh ef         @      * When using this type of function, pay attention to their /reset semantics/. This is discussed later.@@ -196,7 +199,7 @@ 'makeEffectF' [''SomeEff]  -- | Throws an exception when \'SomeAction\' is encountered-runSomeEff :: (@t'Data.Effect.Except.Throw'@ String t'Data.Effect.OpenUnion.<|' ef) => 'Eff' eh (SomeEff ': ef) ~> 'Eff' eh ef+runSomeEff :: (@t'Data.Effect.Except.Throw'@ String t'Data.Effect.OpenUnion.<|' ef) => 'Eff' eh (SomeEff ': ef) t'Control.Effect.~>' 'Eff' eh ef runSomeEff = 'interpret' \\SomeAction -> v'Data.Effect.Except.throw' "not caught"  -- | Catches the exception if \'someAction\' results in one@@ -204,13 +207,13 @@ action = someAction \`@v'Data.Effect.Except.catch'@\` \\(_ :: String) -> 'pure' "caught"  prog1 :: IO ()-prog1 = 'runPure' . runThrow @String . runCatch @String . runSomeEff $ action+prog1 = 'runPure' . runThrow \@String . runCatch \@String . runSomeEff $ action  >>> prog1 Right "caught"  prog2 :: IO ()-prog2 = 'runPure' . runThrow @String . runSomeEff . runCatch @String $ action+prog2 = 'runPure' . runThrow \@String . runSomeEff . runCatch \@String $ action  >>> prog2 Left "not caught"@@ -225,10 +228,10 @@ Let's revisit the definition of @runCatch@:  @-[runCatch](https://hackage.haskell.org/package/heftia-effects-0.4.0.0/docs/Control-Monad-Hefty-Except.html#v:runCatch) :: (@t'Data.Effect.Except.Throw'@ e t'Data.Effect.OpenUnion.<|' ef) => 'Eff' '[@t'Data.Effect.Except.Catch'@ e] ef t'Control.Effect.~>' 'Eff' '[] ef+[runCatch](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-Except.html#v:runCatch) :: (@t'Data.Effect.Except.Throw'@ e t'Data.Effect.OpenUnion.<|' ef) => 'Eff' '[@t'Data.Effect.Except.Catch'@ e] ef t'Control.Effect.~>' 'Eff' '[] ef runCatch = 'interpretH' elabCatch -[elabCatch](https://hackage.haskell.org/package/heftia-effects-0.4.0.0/docs/Control-Monad-Hefty-Except.html#v:elabCatch) :: (@t'Data.Effect.Except.Throw'@ e t'Data.Effect.OpenUnion.<|' ef) => t'Data.Effect.Except.Catch' e t'Control.Monad.Hefty.~~>' 'Eff' '[] ef+[elabCatch](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-Except.html#v:elabCatch) :: (@t'Data.Effect.Except.Throw'@ e t'Data.Effect.OpenUnion.<|' ef) => t'Data.Effect.Except.Catch' e t'Control.Monad.Hefty.~~>' 'Eff' '[] ef elabCatch (@v'Data.Effect.Except.Catch'@ action hdl) = action & 'interposeWith' \\(@v'Data.Effect.Except.Throw'@ e) _ -> hdl e @ @@ -266,7 +269,7 @@ @     runCatch \@String action  =  runCatch \@String $ someAction \`@v'Data.Effect.Except.catch'@\` \\(_ :: String) -> 'pure' "caught"-==> 'interposeWith' (\\(@v'Data.Effect.Except.Throw' e) _ -> 'pure' "caught") $ someAction+==> 'interposeWith' (\\(@v'Data.Effect.Except.Throw'@ e) _ -> 'pure' "caught") $ someAction @  At this point, since there is no v'Data.Effect.Except.throw' in the computation@@ -319,18 +322,18 @@ When performing recursive continuational stateful interpretation, that is, when using functions with @Rec@, it's necessary to understand their semantics. If you are not using @Rec@ functions, you don't need to pay particular attention to this section. -[@runStateRec@](https://hackage.haskell.org/package/heftia-effects-0.4.0.0/docs/Control-Monad-Hefty-State.html#v:runStateRec) is a variant of- [@runState@](https://hackage.haskell.org/package/heftia-effects-0.4.0.0/docs/Control-Monad-Hefty-State.html#v:runState),+[@evalStateRec@](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-State.html#v:evalStateRec) is a variant of+ [@evalState@](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-State.html#v:evalState), a handler for the @State@ effect that can be used even when higher-order effects are unelaborated:  @-[@runStateRec@](https://hackage.haskell.org/package/heftia-effects-0.4.0.0/docs/Control-Monad-Hefty-State.html#v:runStateRec) :: 'Eff' eh (@t'Data.Effect.State.State'@ s ': ef) t'Control.Effect.~>' 'Eff' eh ef-[@runState@](https://hackage.haskell.org/package/heftia-effects-0.4.0.0/docs/Control-Monad-Hefty-State.html#v:runState) :: 'Eff' '[] (@t'Data.Effect.State.State'@ s ': ef) t'Control.Effect.~>' 'Eff' '[] ef+[@evalStateRec@](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-State.html#v:evalStateRec) :: s -> 'Eff' eh (@t'Data.Effect.State.State'@ s ': ef) t'Control.Effect.~>' 'Eff' eh ef+[@evalState@](https://hackage.haskell.org/package/heftia-effects-0.5.0.0/docs/Control-Monad-Hefty-State.html#v:evalState) :: s -> 'Eff' '[] (@t'Data.Effect.State.State'@ s ': ef) t'Control.Effect.~>' 'Eff' '[] ef @ -@runStateRec@ uses @Rec@ functions internally. When a function uses @Rec@ functions internally, it's best to reflect that in its naming.+@evalStateRec@ uses @Rec@ functions internally. When a function uses @Rec@ functions internally, it's best to reflect that in its naming. -Now, if you perform @runStateRec@ before elaborating higher-order effects, the following occurs.+Now, if you perform @evalStateRec@ before elaborating higher-order effects, the following occurs. Note that we are using the @Log@ and @Span@ effects introduced in the first example.  @@@ -338,7 +341,7 @@  prog :: IO () prog = 'runEff' do-    runLog . runSpan . runStateRec \@[Int] [] $ do+    runLog . runSpan . evalStateRec \@[Int] [] $ do          v'Data.Effect.State.modify' \@[Int] (++ [1])         log . show =<< v'Data.Effect.State.get' \@[Int]@@ -367,7 +370,7 @@ if there are unelaborated higher-order effects remaining, resets of this continuational state occur for each scope of those higher-order effects. For higher-order effects that have already been elaborated and removed from the list at that point, there is naturally no impact. -This is simply because @runStateRec@ (generally all @Rec@ functions) recursively applies @runState@ to the scopes of unelaborated higher-order effects.+This is simply because @evalStateRec@ (generally all @Rec@ functions) recursively applies @evalState@ to the scopes of unelaborated higher-order effects. Interpretation occurs independently for each scope, and the state is not carried over.  From the perspective of @shift/reset@ delimited continuations, this phenomenon can be seen as @reset@s being inserted at the scopes of unelaborated higher-order effects.@@ -387,7 +390,7 @@  prog :: IO () prog = 'runEff' do-    runLog . runState \@[Int] [] . runSpan $ do+    runLog . evalState \@[Int] [] . runSpan $ do          v'Data.Effect.State.modify' \@[Int] (++ [1])         log . show =<< v'Data.Effect.State.get' \@[Int]@@ -503,9 +506,10 @@     -- *** For first-order effects     reinterpret,     reinterpretN,-    reinterpretNWith,     reinterpretBy,     reinterpretNBy,+    reinterpretWith,+    reinterpretNWith,     reinterpretRecWith,     reinterpretRecNWith, @@ -538,8 +542,13 @@     iterEffRecHWith,     iterEffRecHFWith,     iterEffHFBy,+    iterAllEffHF,     iterAllEffHFBy, +    -- ** Layer manipulation+    splitLayer,+    mergeLayer,+     -- ** Utilities     stateless, @@ -582,12 +591,14 @@     raise,     raises,     raiseN,+    raiseAll,     raiseUnder,     raisesUnder,     raiseNUnder,     raiseH,     raisesH,     raiseNH,+    raiseAllH,     raiseUnderH,     raiseNUnderH, @@ -627,8 +638,10 @@     tagH,     untagH,     retagH,+    key,     unkey,     rekey,+    keyH,     unkeyH,     rekeyH, @@ -642,7 +655,11 @@     liftIO,     module Data.Effect.OpenUnion,     module Data.Effect,+    module Data.Effect.Tag,+    module Data.Effect.Key,     module Data.Effect.TH,+    module Data.Effect.HFunctor.TH,+    module Data.Effect.Key.TH,     module Control.Effect, ) where @@ -661,6 +678,7 @@     interpretRecHWith,     interpretRecWith,     interpretWith,+    iterAllEffHF,     iterAllEffHFBy,     iterEffBy,     iterEffHBy,@@ -668,6 +686,7 @@     iterEffRecH,     iterEffRecHFWith,     iterEffRecHWith,+    mergeLayer,     reinterpret,     reinterpretBy,     reinterpretH,@@ -683,8 +702,10 @@     reinterpretRecNHWith,     reinterpretRecNWith,     reinterpretRecWith,+    reinterpretWith,     runEff,     runPure,+    splitLayer,     stateless,  ) @@ -706,7 +727,11 @@     bundleN,     bundleUnder,     bundleUnderH,+    key,+    keyH,     raise,+    raiseAll,+    raiseAllH,     raiseH,     raiseN,     raiseNH,@@ -784,7 +809,11 @@ import Control.Monad.IO.Class (liftIO) import Data.Effect import Data.Effect.HFunctor (HFunctor)+import Data.Effect.HFunctor.TH+import Data.Effect.Key+import Data.Effect.Key.TH import Data.Effect.OpenUnion import Data.Effect.OpenUnion.Sum (type (:+:)) import Data.Effect.TH+import Data.Effect.Tag import Data.Kind (Type)

@@ -18,11 +18,15 @@  import Control.Arrow ((>>>)) import Control.Effect (type (~>))+import Control.Monad ((>=>)) import Control.Monad.Hefty.Types (     Eff (Op, Val),     Elaborator,     Interpreter,+    send0,+    sendUnion,     sendUnionBy,+    sendUnionH,     sendUnionHBy,     type (~~>),  )@@ -188,40 +192,40 @@ {-# INLINE reinterpretN #-}  reinterpretWith-    :: forall e ef' ef a+    :: forall e ef' ef eh a      . (ef `IsSuffixOf` ef')-    => Interpreter e (Eff '[] ef') a+    => Interpreter e (Eff eh ef') a     -> Eff '[] (e ': ef) a-    -> Eff '[] ef' a+    -> Eff eh ef' a reinterpretWith = reinterpretBy pure {-# INLINE reinterpretWith #-}  reinterpretNWith-    :: forall n e ef' ef a+    :: forall n e ef' ef eh a      . (WeakenN n ef ef')-    => Interpreter e (Eff '[] ef') a+    => Interpreter e (Eff eh ef') a     -> Eff '[] (e ': ef) a-    -> Eff '[] ef' a+    -> Eff eh ef' a reinterpretNWith = reinterpretNBy @n pure {-# INLINE reinterpretNWith #-}  reinterpretBy-    :: forall e ef' ef ans a+    :: forall e ef' ef eh ans a      . (ef `IsSuffixOf` ef')-    => (a -> Eff '[] ef' ans)-    -> Interpreter e (Eff '[] ef') ans+    => (a -> Eff eh ef' ans)+    -> Interpreter e (Eff eh ef') ans     -> Eff '[] (e ': ef) a-    -> Eff '[] ef' ans+    -> Eff eh ef' ans reinterpretBy ret hdl = iterAllEffHFBy ret nilH (hdl !+ flip sendUnionBy . weakens) {-# INLINE reinterpretBy #-}  reinterpretNBy-    :: forall n e ef' ef ans a+    :: forall n e ef' ef eh ans a      . (WeakenN n ef ef')-    => (a -> Eff '[] ef' ans)-    -> Interpreter e (Eff '[] ef') ans+    => (a -> Eff eh ef' ans)+    -> Interpreter e (Eff eh ef') ans     -> Eff '[] (e ': ef) a-    -> Eff '[] ef' ans+    -> Eff eh ef' ans reinterpretNBy ret hdl = iterAllEffHFBy ret nilH (hdl !+ flip sendUnionBy . weakenN @n) {-# INLINE reinterpretNBy #-} @@ -373,14 +377,14 @@ If multiple instances of @e@ exist in the list, the one closest to the head (with the smallest index) will be targeted. -} interposeBy-    :: forall e ef ans a+    :: forall e ef eh ans a      . (e <| ef)-    => (a -> Eff '[] ef ans)+    => (a -> Eff eh ef ans)     -- ^ Value handler-    -> Interpreter e (Eff '[] ef) ans+    -> Interpreter e (Eff eh ef) ans     -- ^ Effect handler     -> Eff '[] ef a-    -> Eff '[] ef ans+    -> Eff eh ef ans interposeBy ret f = iterAllEffHFBy ret nilH \u -> maybe (`sendUnionBy` u) f (prj @e u) {-# INLINE interposeBy #-} @@ -561,6 +565,38 @@           where             k = loop . qApp q {-# INLINE iterAllEffHFBy #-}++-- | Traverses all effects using the provided natural-transformation style elaborator and handler, transforming them into a monad @m@.+iterAllEffHF+    :: forall eh ef m+     . (Monad m)+    => UnionH eh ~~> m+    -- ^ Effect elaborator+    -> Union ef ~> m+    -- ^ Effect handler+    -> Eff eh ef ~> m+iterAllEffHF fh ff = loop+  where+    loop :: Eff eh ef ~> m+    loop = \case+        Val x -> pure x+        Op u q -> either (fh . hfmapUnion loop >=> k) (ff >=> k) u+          where+            k = loop . qApp q+{-# INLINE iterAllEffHF #-}++-- * Layer manipulation++splitLayer :: Eff '[] ef ~> Eff eh '[Eff '[] ef]+splitLayer =+    iterAllEffHFBy pure nilH (\u k -> send0 (sendUnion u) >>= k)++mergeLayer :: Eff eh '[Eff eh ef] ~> Eff eh ef+mergeLayer =+    iterAllEffHFBy+        pure+        (\u k -> sendUnionH (hfmapUnion mergeLayer u) >>= k)+        (\u k -> extract u >>= k)  -- * Utilities 

@@ -39,6 +39,7 @@     bundleUnionUnder,     decomp,     inj,+    nil,     prj,     strengthen,     strengthenN,@@ -66,6 +67,7 @@     decompH,     hfmapUnion,     injH,+    nilH,     prjH,     strengthenH,     strengthenNH,@@ -220,6 +222,11 @@ raiseN = transEff (weakenN @len) {-# INLINE raiseN #-} +-- | Raises an empty first-order effect list to an arbitrary effect list.+raiseAll :: Eff eh '[] ~> Eff eh ef+raiseAll = transEff nil+{-# INLINE raiseAll #-}+ {- | Inserts an arbitrary first-order effect @e2@ just below the head of the list. -}@@ -273,6 +280,11 @@ raiseNH = transEffH (weakenNH @len) {-# INLINE raiseNH #-} +-- | Raises an empty first-order effect list to an arbitrary effect list.+raiseAllH :: Eff '[] ef ~> Eff eh ef+raiseAllH = transEffH nilH+{-# INLINE raiseAllH #-}+ {- | Inserts an arbitrary higher-order effect @e2@ just below the head of the list. -}@@ -581,6 +593,13 @@ retagH = transformH $ TagH . unTagH {-# INLINE retagH #-} +-- | Attaches the @key@ to the first-order effect at the head of the list.+key+    :: forall key e ef eh+     . Eff eh (e ': ef) ~> Eff eh (key #> e ': ef)+key = transform Key+{-# INLINE key #-}+ -- | Removes the @key@ from the keyed first-order effect at the head of the list. unkey     :: forall key e ef eh@@ -596,6 +615,14 @@      . Eff eh (key #> e ': ef) ~> Eff eh (key' #> e ': ef) rekey = transform $ Key . unKey {-# INLINE rekey #-}++-- | Attaches the @key@ to the higher-order effect at the head of the list.+keyH+    :: forall key e ef eh+     . (HFunctor e)+    => Eff (e ': eh) ef ~> Eff (key ##> e ': eh) ef+keyH = transformH KeyH+{-# INLINE keyH #-}  -- | Removes the @key@ from the keyed higher-order effect at the head of the list. unkeyH

@@ -15,6 +15,7 @@ -} module Data.Effect.OpenUnion.Internal where +import Data.Effect.Key (type (##>), type (#>)) import Data.Proxy (Proxy (Proxy)) import Data.Type.Equality (type (==)) import GHC.TypeError (ErrorMessage (ShowType, Text, (:$$:), (:<>:)), TypeError)@@ -68,13 +69,23 @@ -} instance {-# INCOHERENT #-} IfNotFound e r w -type LookupError (key :: kk) (w :: [ke]) =-    TypeError+class IfKeyNotFound (key :: k) (r :: [e]) (w :: [e])++instance+    ( TypeError         ( 'Text "The key ‘"             ':<>: 'ShowType key             ':<>: 'Text "’ does not exist in the type-level list"             ':$$: 'Text "  ‘" ':<>: 'ShowType w ':<>: 'Text "’"         )+    )+    => IfKeyNotFound key '[] w++instance IfKeyNotFound key (key #> e ': r) w+instance IfKeyNotFound key (key ##> e ': r) w+instance {-# OVERLAPPABLE #-} (IfKeyNotFound key r w) => IfKeyNotFound key (e ': r) w++instance {-# INCOHERENT #-} IfKeyNotFound e r w  infixr 5 ++ type family xs ++ ys where

@@ -31,11 +31,11 @@     ElemAt,     ElemIndex,     FindElem,+    IfKeyNotFound,     IfNotFound,     IsSuffixOf,     KnownLength,     Length,-    LookupError,     P (unP),     PrefixLength,     Reverse,@@ -153,14 +153,11 @@ infix 3 <| type (<|) = Member -type MemberBy key e es = (key #> e <| es, Lookup key es ~ key #> e)--type Lookup key es = Lookup_ key es es+type MemberBy key e es = (key #> e <| es, Lookup key es ~ key #> e, IfKeyNotFound key es es) -type family Lookup_ (key :: k) r w :: EffectF where-    Lookup_ key (key #> e ': _) w = key #> e-    Lookup_ key (_ ': r) w = Lookup_ key r w-    Lookup_ key '[] w = LookupError key w+type family Lookup (key :: k) r :: EffectF where+    Lookup key (key #> e ': _) = key #> e+    Lookup key (_ ': r) = Lookup key r  {- | Orthogonal decomposition of a @'Union' (e ': es) :: 'EffectF'@. 'Right' value is returned if the @'Union' (e ': es) :: 'EffectF'@ contains @e :: 'EffectF'@, and

@@ -36,11 +36,11 @@     ElemAt,     ElemIndex,     FindElem,+    IfKeyNotFound,     IfNotFound,     IsSuffixOf,     KnownLength,     Length,-    LookupError,     P (unP),     PrefixLength,     Reverse,@@ -110,14 +110,11 @@ infix 3 <<| type (<<|) = MemberH -type MemberHBy key e es = (key ##> e <<| es, LookupH key es ~ key ##> e)--type LookupH key es = LookupH_ key es es+type MemberHBy key e es = (key ##> e <<| es, LookupH key es ~ key ##> e, IfKeyNotFound key es es) -type family LookupH_ (key :: k) r w :: EffectH where-    LookupH_ key (key ##> e ': _) w = key ##> e-    LookupH_ key (_ ': r) w = LookupH_ key r w-    LookupH_ key '[] w = LookupError key w+type family LookupH (key :: k) r :: EffectH where+    LookupH key (key ##> e ': _) = key ##> e+    LookupH key (_ ': r) = LookupH key r  decompH :: (HFunctor e) => UnionH (e ': es) f a -> Either (UnionH es f a) (e f a) decompH (UnionH 0 a koi) = Right $ hfmap koi $ unsafeCoerce a

@@ -0,0 +1,76 @@+{- |+Module:       Data.FTCQueue+Description:  Fast type-aligned queue optimized to effectful functions.+Copyright:    (c) 2016 Allele Dev; 2017 Ixperta Solutions s.r.o.; 2017 Alexis King+License:      BSD3+Maintainer:   Alexis King <lexi.lambda@gmail.com>+Stability:    experimental+Portability:  GHC specific language extensions.++* Constant-time append\/('><') and snoc\/('|>')+* Average constant-time 'viewL' (left-edge deconstruction).++Using <http://okmij.org/ftp/Haskell/extensible/FTCQueue1.hs> as a starting+point.++A minimal version of FTCQueue from "Reflection w/o Remorse":++* Research: <http://okmij.org/ftp/Haskell/Reflection.html>+* <https://hackage.haskell.org/package/type-aligned type-aligned> (FTCQueue)+-}+module Data.FTCQueue (+    FTCQueue,+    tsingleton,+    (|>),+    snoc,+    (><),+    append,+    ViewL (..),+    tviewl,+) where++{- | Non-empty tree. Deconstruction operations make it more and more+left-leaning+-}+data FTCQueue m a b where+    Leaf :: (a -> m b) -> FTCQueue m a b+    Node :: FTCQueue m a x -> FTCQueue m x b -> FTCQueue m a b++-- | Build a leaf from a single operation. [O(1)]+tsingleton :: (a -> m b) -> FTCQueue m a b+tsingleton = Leaf+{-# INLINE tsingleton #-}++-- | Append an operation to the right of the tree. [O(1)]+(|>) :: FTCQueue m a x -> (x -> m b) -> FTCQueue m a b+t |> r = Node t (Leaf r)+{-# INLINE (|>) #-}++-- | An alias for '(|>)'+snoc :: FTCQueue m a x -> (x -> m b) -> FTCQueue m a b+snoc = (|>)+{-# INLINE snoc #-}++-- | Append two trees of operations. [O(1)]+(><) :: FTCQueue m a x -> FTCQueue m x b -> FTCQueue m a b+t1 >< t2 = Node t1 t2+{-# INLINE (><) #-}++-- | An alias for '(><)'+append :: FTCQueue m a x -> FTCQueue m x b -> FTCQueue m a b+append = (><)+{-# INLINE append #-}++-- | Left view deconstruction data structure.+data ViewL m a b where+    TOne :: (a -> m b) -> ViewL m a b+    (:|) :: (a -> m x) -> FTCQueue m x b -> ViewL m a b++-- | Left view deconstruction. [average O(1)]+tviewl :: FTCQueue m a b -> ViewL m a b+tviewl (Leaf r) = TOne r+tviewl (Node t1 t2) = go t1 t2+  where+    go :: FTCQueue m a x -> FTCQueue m x b -> ViewL m a b+    go (Leaf r) tr = r :| tr+    go (Node tl1 tl2) tr = go tl1 (Node tl2 tr)