Script 'mail_helper' called by obssrc
Hello community,
here is the log from the commit of package ghc-recursion-schemes for
openSUSE:Factory checked in at 2021-03-10 08:56:27
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Comparing /work/SRC/openSUSE:Factory/ghc-recursion-schemes (Old)
and /work/SRC/openSUSE:Factory/.ghc-recursion-schemes.new.2378 (New)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "ghc-recursion-schemes"
Wed Mar 10 08:56:27 2021 rev:3 rq:877985 version:5.2.2
Changes:
--------
---
/work/SRC/openSUSE:Factory/ghc-recursion-schemes/ghc-recursion-schemes.changes
2020-12-22 11:45:06.625797362 +0100
+++
/work/SRC/openSUSE:Factory/.ghc-recursion-schemes.new.2378/ghc-recursion-schemes.changes
2021-03-10 08:58:10.958946415 +0100
@@ -1,0 +2,10 @@
+Sun Feb 21 12:48:08 UTC 2021 - [email protected]
+
+- Update recursion-schemes to version 5.2.2.
+ ## 5.2.2
+ * More Mendler-style recursion-schemes: `mpara`, `mzygo`, `mana`, `mapo`, and
+ `mfutu`.
+ * `makeBaseFunctor` no longer generates warnings when combined with
+ DerivingStrategies.
+
+-------------------------------------------------------------------
Old:
----
recursion-schemes-5.2.1.tar.gz
New:
----
recursion-schemes-5.2.2.tar.gz
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Other differences:
------------------
++++++ ghc-recursion-schemes.spec ++++++
--- /var/tmp/diff_new_pack.27VUBh/_old 2021-03-10 08:58:11.774947257 +0100
+++ /var/tmp/diff_new_pack.27VUBh/_new 2021-03-10 08:58:11.778947261 +0100
@@ -1,7 +1,7 @@
#
# spec file for package ghc-recursion-schemes
#
-# Copyright (c) 2020 SUSE LLC
+# Copyright (c) 2021 SUSE LLC
#
# All modifications and additions to the file contributed by third parties
# remain the property of their copyright owners, unless otherwise agreed
@@ -19,7 +19,7 @@
%global pkg_name recursion-schemes
%bcond_with tests
Name: ghc-%{pkg_name}
-Version: 5.2.1
+Version: 5.2.2
Release: 0
Summary: Representing common recursion patterns as higher-order
functions
License: BSD-2-Clause
@@ -27,6 +27,7 @@
Source0:
https://hackage.haskell.org/package/%{pkg_name}-%{version}/%{pkg_name}-%{version}.tar.gz
BuildRequires: ghc-Cabal-devel
BuildRequires: ghc-base-orphans-devel
+BuildRequires: ghc-cabal-doctest-devel
BuildRequires: ghc-comonad-devel
BuildRequires: ghc-containers-devel
BuildRequires: ghc-data-fix-devel
++++++ recursion-schemes-5.2.1.tar.gz -> recursion-schemes-5.2.2.tar.gz ++++++
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/recursion-schemes-5.2.1/.travis.yml
new/recursion-schemes-5.2.2/.travis.yml
--- old/recursion-schemes-5.2.1/.travis.yml 2001-09-09 03:46:40.000000000
+0200
+++ new/recursion-schemes-5.2.2/.travis.yml 1970-01-01 01:00:00.000000000
+0100
@@ -1,167 +0,0 @@
-# This Travis job script has been generated by a script via
-#
-# haskell-ci '--output=.travis.yml' '--config=cabal.haskell-ci'
'cabal.project'
-#
-# To regenerate the script (for example after adjusting tested-with) run
-#
-# haskell-ci regenerate
-#
-# For more information, see https://github.com/haskell-CI/haskell-ci
-#
-# version: 0.10.2
-#
-version: ~> 1.0
-language: c
-os: linux
-dist: xenial
-git:
- # whether to recursively clone submodules
- submodules: false
-notifications:
- irc:
- channels:
- - irc.freenode.org#haskell-lens
- skip_join: true
- template:
- - "\x0313recursion-schemes\x03/\x0306%{branch}\x03 \x0314%{commit}\x03
%{build_url} %{message}"
-cache:
- directories:
- - $HOME/.cabal/packages
- - $HOME/.cabal/store
- - $HOME/.hlint
-before_cache:
- - rm -fv $CABALHOME/packages/hackage.haskell.org/build-reports.log
- # remove files that are regenerated by 'cabal update'
- - rm -fv $CABALHOME/packages/hackage.haskell.org/00-index.*
- - rm -fv $CABALHOME/packages/hackage.haskell.org/*.json
- - rm -fv $CABALHOME/packages/hackage.haskell.org/01-index.cache
- - rm -fv $CABALHOME/packages/hackage.haskell.org/01-index.tar
- - rm -fv $CABALHOME/packages/hackage.haskell.org/01-index.tar.idx
- - rm -rfv $CABALHOME/packages/head.hackage
-jobs:
- include:
- - compiler: ghc-8.10.1
- addons: {"apt":{"sources":[{"sourceline":"deb
http://ppa.launchpad.net/hvr/ghc/ubuntu xenial
main","key_url":"https://keyserver.ubuntu.com/pks/lookup?op=get&search=0x063dab2bdc0b3f9fcebc378bff3aeacef6f88286"}],"packages":["ghc-8.10.1","cabal-install-3.2"]}}
- os: linux
- - compiler: ghc-8.8.3
- addons: {"apt":{"sources":[{"sourceline":"deb
http://ppa.launchpad.net/hvr/ghc/ubuntu xenial
main","key_url":"https://keyserver.ubuntu.com/pks/lookup?op=get&search=0x063dab2bdc0b3f9fcebc378bff3aeacef6f88286"}],"packages":["ghc-8.8.3","cabal-install-3.2"]}}
- os: linux
- - compiler: ghc-8.6.5
- addons: {"apt":{"sources":[{"sourceline":"deb
http://ppa.launchpad.net/hvr/ghc/ubuntu xenial
main","key_url":"https://keyserver.ubuntu.com/pks/lookup?op=get&search=0x063dab2bdc0b3f9fcebc378bff3aeacef6f88286"}],"packages":["ghc-8.6.5","cabal-install-3.2"]}}
- os: linux
- - compiler: ghc-8.4.4
- addons: {"apt":{"sources":[{"sourceline":"deb
http://ppa.launchpad.net/hvr/ghc/ubuntu xenial
main","key_url":"https://keyserver.ubuntu.com/pks/lookup?op=get&search=0x063dab2bdc0b3f9fcebc378bff3aeacef6f88286"}],"packages":["ghc-8.4.4","cabal-install-3.2"]}}
- os: linux
- - compiler: ghc-8.2.2
- addons: {"apt":{"sources":[{"sourceline":"deb
http://ppa.launchpad.net/hvr/ghc/ubuntu xenial
main","key_url":"https://keyserver.ubuntu.com/pks/lookup?op=get&search=0x063dab2bdc0b3f9fcebc378bff3aeacef6f88286"}],"packages":["ghc-8.2.2","cabal-install-3.2"]}}
- os: linux
- - compiler: ghc-8.0.2
- addons: {"apt":{"sources":[{"sourceline":"deb
http://ppa.launchpad.net/hvr/ghc/ubuntu xenial
main","key_url":"https://keyserver.ubuntu.com/pks/lookup?op=get&search=0x063dab2bdc0b3f9fcebc378bff3aeacef6f88286"}],"packages":["ghc-8.0.2","cabal-install-3.2"]}}
- os: linux
- - compiler: ghc-7.10.3
- addons: {"apt":{"sources":[{"sourceline":"deb
http://ppa.launchpad.net/hvr/ghc/ubuntu xenial
main","key_url":"https://keyserver.ubuntu.com/pks/lookup?op=get&search=0x063dab2bdc0b3f9fcebc378bff3aeacef6f88286"}],"packages":["ghc-7.10.3","cabal-install-3.2"]}}
- os: linux
- - compiler: ghc-7.8.4
- addons: {"apt":{"sources":[{"sourceline":"deb
http://ppa.launchpad.net/hvr/ghc/ubuntu xenial
main","key_url":"https://keyserver.ubuntu.com/pks/lookup?op=get&search=0x063dab2bdc0b3f9fcebc378bff3aeacef6f88286"}],"packages":["ghc-7.8.4","cabal-install-3.2"]}}
- os: linux
- - compiler: ghc-7.6.3
- addons: {"apt":{"sources":[{"sourceline":"deb
http://ppa.launchpad.net/hvr/ghc/ubuntu xenial
main","key_url":"https://keyserver.ubuntu.com/pks/lookup?op=get&search=0x063dab2bdc0b3f9fcebc378bff3aeacef6f88286"}],"packages":["ghc-7.6.3","cabal-install-3.2"]}}
- os: linux
- - compiler: ghc-7.4.2
- addons: {"apt":{"sources":[{"sourceline":"deb
http://ppa.launchpad.net/hvr/ghc/ubuntu xenial
main","key_url":"https://keyserver.ubuntu.com/pks/lookup?op=get&search=0x063dab2bdc0b3f9fcebc378bff3aeacef6f88286"}],"packages":["ghc-7.4.2","cabal-install-3.2"]}}
- os: linux
-before_install:
- - HC=$(echo "/opt/$CC/bin/ghc" | sed 's/-/\//')
- - WITHCOMPILER="-w $HC"
- - HADDOCK=$(echo "/opt/$CC/bin/haddock" | sed 's/-/\//')
- - HCPKG="$HC-pkg"
- - unset CC
- - CABAL=/opt/ghc/bin/cabal
- - CABALHOME=$HOME/.cabal
- - export PATH="$CABALHOME/bin:$PATH"
- - TOP=$(pwd)
- - "HCNUMVER=$(${HC} --numeric-version|perl -ne
'/^(\\d+)\\.(\\d+)\\.(\\d+)(\\.(\\d+))?$/; print(10000 * $1 + 100 * $2 + ($3 ==
0 ? $5 != 1 : $3))')"
- - echo $HCNUMVER
- - CABAL="$CABAL -vnormal+nowrap"
- - set -o pipefail
- - TEST=--enable-tests
- - BENCH=--enable-benchmarks
- - HEADHACKAGE=false
- - rm -f $CABALHOME/config
- - |
- echo "verbose: normal +nowrap +markoutput" >> $CABALHOME/config
- echo "remote-build-reporting: anonymous" >> $CABALHOME/config
- echo "write-ghc-environment-files: always" >> $CABALHOME/config
- echo "remote-repo-cache: $CABALHOME/packages" >> $CABALHOME/config
- echo "logs-dir: $CABALHOME/logs" >> $CABALHOME/config
- echo "world-file: $CABALHOME/world" >> $CABALHOME/config
- echo "extra-prog-path: $CABALHOME/bin" >> $CABALHOME/config
- echo "symlink-bindir: $CABALHOME/bin" >> $CABALHOME/config
- echo "installdir: $CABALHOME/bin" >> $CABALHOME/config
- echo "build-summary: $CABALHOME/logs/build.log" >> $CABALHOME/config
- echo "store-dir: $CABALHOME/store" >> $CABALHOME/config
- echo "install-dirs user" >> $CABALHOME/config
- echo " prefix: $CABALHOME" >> $CABALHOME/config
- echo "repository hackage.haskell.org" >> $CABALHOME/config
- echo " url: http://hackage.haskell.org/"; >> $CABALHOME/config
-install:
- - ${CABAL} --version
- - echo "$(${HC} --version) [$(${HC} --print-project-git-commit-id 2>
/dev/null || echo '?')]"
- - |
- echo "program-default-options" >> $CABALHOME/config
- echo " ghc-options: $GHCJOBS +RTS -M6G -RTS" >> $CABALHOME/config
- - cat $CABALHOME/config
- - rm -fv cabal.project cabal.project.local cabal.project.freeze
- - travis_retry ${CABAL} v2-update -v
- - if [ $HCNUMVER -ge 80000 ] ; then ${CABAL} v2-install $WITHCOMPILER
--ignore-project -j2 doctest --constraint='doctest ^>=0.17' ; fi
- # Generate cabal.project
- - rm -rf cabal.project cabal.project.local cabal.project.freeze
- - touch cabal.project
- - |
- echo "packages: ." >> cabal.project
- - if [ $HCNUMVER -ge 80200 ] ; then echo 'package recursion-schemes' >>
cabal.project ; fi
- - "if [ $HCNUMVER -ge 80200 ] ; then echo ' ghc-options:
-Werror=missing-methods' >> cabal.project ; fi"
- - |
- - "for pkg in $($HCPKG list --simple-output); do echo $pkg | sed
's/-[^-]*$//' | (grep -vE -- '^(recursion-schemes)$' || true) | sed
's/^/constraints: /' | sed 's/$/ installed/' >> cabal.project.local; done"
- - cat cabal.project || true
- - cat cabal.project.local || true
- - if [ -f "./configure.ac" ]; then (cd "." && autoreconf -i); fi
- - ${CABAL} v2-freeze $WITHCOMPILER ${TEST} ${BENCH}
- - "cat cabal.project.freeze | sed -E 's/^(constraints: *| *)//' | sed
's/any.//'"
- - rm cabal.project.freeze
- - travis_wait 40 ${CABAL} v2-build $WITHCOMPILER ${TEST} ${BENCH} --dep -j2
all
-script:
- - DISTDIR=$(mktemp -d /tmp/dist-test.XXXX)
- # Packaging...
- - ${CABAL} v2-sdist all
- # Unpacking...
- - mv dist-newstyle/sdist/*.tar.gz ${DISTDIR}/
- - cd ${DISTDIR} || false
- - find . -maxdepth 1 -type f -name '*.tar.gz' -exec tar -xvf '{}' \;
- - find . -maxdepth 1 -type f -name '*.tar.gz' -exec rm '{}' \;
- - PKGDIR_recursion_schemes="$(find . -maxdepth 1 -type d -regex
'.*/recursion-schemes-[0-9.]*')"
- # Generate cabal.project
- - rm -rf cabal.project cabal.project.local cabal.project.freeze
- - touch cabal.project
- - |
- echo "packages: ${PKGDIR_recursion_schemes}" >> cabal.project
- - if [ $HCNUMVER -ge 80200 ] ; then echo 'package recursion-schemes' >>
cabal.project ; fi
- - "if [ $HCNUMVER -ge 80200 ] ; then echo ' ghc-options:
-Werror=missing-methods' >> cabal.project ; fi"
- - |
- - "for pkg in $($HCPKG list --simple-output); do echo $pkg | sed
's/-[^-]*$//' | (grep -vE -- '^(recursion-schemes)$' || true) | sed
's/^/constraints: /' | sed 's/$/ installed/' >> cabal.project.local; done"
- - cat cabal.project || true
- - cat cabal.project.local || true
- # Building with tests and benchmarks...
- # build & run tests, build benchmarks
- - ${CABAL} v2-build $WITHCOMPILER ${TEST} ${BENCH} all
- # Testing...
- - ${CABAL} v2-test $WITHCOMPILER ${TEST} ${BENCH} all
- # Doctest...
- - if [ $HCNUMVER -ge 80000 ] ; then (cd ${PKGDIR_recursion_schemes} &&
doctest -DCURRENT_PACKAGE_KEY='"recursion-schemes"' -this-unit-id
recursion-schemes src) ; fi
- # cabal check...
- - (cd ${PKGDIR_recursion_schemes} && ${CABAL} -vnormal check)
- # haddock...
- - ${CABAL} v2-haddock $WITHCOMPILER --with-haddock $HADDOCK ${TEST} ${BENCH}
all
-
-# REGENDATA
("0.10.2",["--output=.travis.yml","--config=cabal.haskell-ci","cabal.project"])
-# EOF
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/recursion-schemes-5.2.1/CHANGELOG.markdown
new/recursion-schemes-5.2.2/CHANGELOG.markdown
--- old/recursion-schemes-5.2.1/CHANGELOG.markdown 2001-09-09
03:46:40.000000000 +0200
+++ new/recursion-schemes-5.2.2/CHANGELOG.markdown 2001-09-09
03:46:40.000000000 +0200
@@ -1,3 +1,9 @@
+## 5.2.2
+* More Mendler-style recursion-schemes: `mpara`, `mzygo`, `mana`, `mapo`, and
+ `mfutu`.
+* `makeBaseFunctor` no longer generates warnings when combined with
+ DerivingStrategies.
+
## 5.2.1 [2020.10.04]
* Allow building with `template-haskell-2.17.0.0` (GHC 9.0).
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/recursion-schemes-5.2.1/README.markdown
new/recursion-schemes-5.2.2/README.markdown
--- old/recursion-schemes-5.2.1/README.markdown 2001-09-09 03:46:40.000000000
+0200
+++ new/recursion-schemes-5.2.2/README.markdown 2001-09-09 03:46:40.000000000
+0200
@@ -1,37 +1,160 @@
# recursion-schemes
-[](https://hackage.haskell.org/package/recursion-schemes)
[](http://travis-ci.org/ekmett/recursion-schemes)
+[](https://hackage.haskell.org/package/recursion-schemes)
[](https://github.com/ekmett/recursion-schemes/actions?query=workflow%3AHaskell-CI)
-## What is a recursion scheme?
+This package represents common recursion patterns as higher-order functions.
-Many recursive functions share the same structure, e.g. pattern-match on the
input and, depending on the data constructor, either recur on a smaller input
or terminate the recursion with the base case. Another one: start with a seed
value, use it to produce the first element of an infinite list, and recur on a
modified seed in order to produce the rest of the list. Such a structure is
called a recursion scheme.
+## A familiar example
-## Benefits
+Here are two recursive functions.
-### Clearer
+```haskell
+sum :: [Int] -> Int
+sum [] = 0
+sum (x:xs) = x + sum xs
-Each recursion scheme has a unique name, such as "fold" and "unfold"; or, if
you prefer the fancy names, "catamorphism" and "anamorphism". If you program
with others, it can be useful to have names to refer to those recursion
patterns, so you can discuss which type of recursion is the most appropriate
for the problem at hand. Even if you program alone, having names with which to
clearly label those different solutions can help to structure your thoughts
while writing recursive functions.
+product :: [Int] -> Int
+product [] = 1
+product (x:xs) = x * product xs
+```
-This library lists the most common recursion schemes, and also provides an
implementation corresponding to each one. The idea is that a recursive function
may be broken into two parts: the part which is the same in all the recursive
functions which follow a given recursion scheme, and the part which is
different in each function. Our implementation performs the recursive, common
part, and takes as input a function which performs the non-recursive, unique
part.
+These functions are very similar. In both cases, the empty list is the base
case. In the cons case, each makes a recursive call on the tail of the list.
Then, the head of the list is combined with the result using a binary function.
-If you use those implementations instead of making explicit recursive calls,
your code will simultaneously become clearer (to those who are familiar with
recursion schemes) and more obscure (to those who aren't). Obviously, if one
knows how to read and understand recursive code but does not know what e.g.
`para` means, then the version which uses `para` will look needlessly
obfuscated compared to the version they already know how to read. But if one is
familiar with `para`, then seeing this familiar name will instantly clarify
that this is a path-copying function in the style of `Map.insert`, which
allocates new nodes along a path from a node to the root but leaves the rest of
the nodes untouched. This is a very useful starting point, guiding the reader
to look for the logic which decides which sub-trees to drill through and which
sub-trees to leave untouched. In contrast, with the general-recursion version,
the reader has no such starting point and must thus read through the entire
function (or guess based on the function's name) before they can infer that
kind of big picture information.
+We can abstract over those similarities using a higher-order function,
[`foldr`](https://hackage.haskell.org/package/base/docs/Data-List.html#v:foldr):
-### Faster
+```haskell
+sum = foldr (+) 0
+product = foldr (*) 1
+```
-Using recursion schemes can guide you towards optimizations. When multiple
functions are composed, Haskellers often use equational reasoning in order to
rearrange those compositions into equivalent compositions which compute the
same result, but do so in a different, possibly more efficient manner. When the
recursive and non-recursive portions of a function are written separately, more
equations become available, as they have more pieces to work with. The paper
[Functional Programming with Bananas, Lenses, Envelopes and Barbed
Wire](https://maartenfokkinga.github.io/utwente/mmf91m.pdf) has a lot more
details on that subject.
+## Other recursive types
-### Safer
+`foldr` works great for lists. The higher-order functions provided by this
library help with other recursive datatypes. Here are two recursive functions
on
[`Tree`s](https://hackage.haskell.org/package/containers/docs/Data-Tree.html#t:Tree):
-Using recursion schemes can help you to avoid accidentally writing infinite or
non-productive loops. For example, when producing an infinite list, it would be
a mistake to look at the result of the recursive call in order to decide which
element to produce as the head of the list, because that recursive call will
itself look at its recursive call, etc., and so the information will never be
returned. With `ana`, the non-recursive function you need to provide as input
intentionally does not have access to the result of the recursive call, so you
cannot make that mistake.
+```haskell
+depth :: Tree a -> Int
+depth (Node _ subTrees) = 1 + maximum subTrees
-### Composable
+size :: Tree a -> Int
+size (Node _ subTrees) = 1 + sum subTrees
+```
-Many recursion schemes can be implemented in terms of each other. So if you
notice that the non-recursive functions you provide themselves seem to share a
common pattern, you might be accidentally reimplementing an existing recursion
scheme which already has those common parts builtin; or maybe you have stumbled
upon a new recursion scheme which does not yet have a name, and which you may
want to implement yourself.
+It is not possible to use `foldr` to simplify `depth`. Conceptually, `foldr`
is flattening all the elements of the tree into a list before combining them
with the binary function. This does not work for `depth` because it needs to
examine the structure of the tree, which `foldr` flattened away.
-One way to implement such a custom recursion scheme is to combine the features
of existing recursion schemes. For example, a "paramorphism" gives the
non-recursive function access to the original sub-trees, a "zygomorphism" gives
that function access to auxiliary results computed from those sub-trees, and so
the combined "zygomorphic paramorphism" gives that function access to both the
original sub-trees and the auxiliary results. In order to construct such
combinations, most of our recursion schemes come in a generalized variant, e.g.
`gzygo`, and in a "distributive law transformer" variant, e.g. `distZygoT`.
Just like monad transformers, distributive law transformers can be combined
into stacks, and like monad transformers, the order in which you combine the
layers determines how the layers interact with each other. Apply a generalized
recursion scheme to a stack of distributive laws in order to obtain a recursion
scheme which has both the features of the generalized recursion sch
eme and those of the distributive laws.
+We can instead use one of the higher-order functions provided by this library,
[`cata`](https://hackage.haskell.org/package/recursion-schemes/docs/Data-Functor-Foldable.html#v:cata).
-## Contributing
+```haskell
+import Data.Functor.Base (TreeF(..))
+import Data.Functor.Foldable
+
+-- data Tree a = Node a [Tree a]
+-- data TreeF a r = NodeF a [r ]
+
+depth :: Tree a -> Int
+depth = cata go
+ where
+ go :: TreeF a Int -> Int
+ go (NodeF _ subDepths) = 1 + maximum subDepths
+
+size :: Tree a -> Int
+size = cata go
+ where
+ go :: TreeF a Int -> Int
+ go (NodeF _ subSizes) = 1 + sum subSizes
+```
+
+In this example, the code is a bit longer, but it is correct. Did you spot the
mistake in the version which does not use `cata`? We forgot a call to `fmap`:
+
+```haskell
+depth :: Tree a -> Int
+depth (Node _ subTrees) = 1 + maximum (fmap depth subTrees)
+
+size :: Tree a -> Int
+size (Node _ subTrees) = 1 + sum (fmap size subTrees)
+```
+
+`cata` automatically adds this call to `fmap`. This is why `subDepths`
contains a list of already-computed depths, not a list of sub-trees. In
general, each recursive position is replaced by the result of a recursive call.
These results have type `Int`, not type `Tree`, so we need a helper datatype
`TreeF` to collect these results.
+
+When you think about computing the depth, you probably think "it's 1 plus the
maximum of the sub-depths". With `cata`, this is exactly what we write. By
contrast, without `cata`, we need to describe both the "how" and the "what" in
our implementation. The "how" is about recurring over the sub-trees (using
`fmap depth`), while the "what" is about adding 1 to the maximum of the
sub-trees. `cata` takes care of the recursion, so you can focus solely on the
"what".
+
+A **recursion-scheme** is a function like `cata` which implements a common
recursion pattern. It is a higher-order recursive function which takes a
non-recursive function as an argument. That non-recursive function describes
the part which is unique to your calculation: the "what".
+
+## Types with many constructors
+
+Let's look at a more complex example. Here is a small lambda-calculus and a
function to compute the [free
variables](https://en.wikipedia.org/wiki/Lambda_calculus#Free_variables) of an
expression:
+
+```haskell
+import Data.Set (Set)
+import qualified Data.Set as Set
+
+data Expr
+ = Var String
+ | Lam String Expr
+ | App Expr Expr
+ | Constant Int
+ | Add Expr Expr
+ | Sub Expr Expr
+ | Mul Expr Expr
+ | Div Expr Expr
+ | ...
-Contributions and bug reports are welcome!
+freeVars :: Expr -> Set String
+freeVars (Var name) = Set.singleton name
+freeVars (Lam name body) = Set.difference (freeVars body) (Set.singleton name)
+freeVars (App e1 e2) = Set.union (freeVars e1) (freeVars e2)
+freeVars (Constant _) = Set.empty
+freeVars (Add e1 e2) = Set.union (freeVars e1) (freeVars e2)
+freeVars (Sub e1 e2) = Set.union (freeVars e1) (freeVars e2)
+freeVars (Mul e1 e2) = Set.union (freeVars e1) (freeVars e2)
+freeVars (Div e1 e2) = Set.union (freeVars e1) (freeVars e2)
+freeVars ...
+```
+
+As you can see, we had to repeat the `Set.union (freeVars e1) (freeVars e2)`
line over and over. With recursion-schemes, this code becomes much shorter:
+
+```haskell
+{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable,
TemplateHaskell, TypeFamilies #-}
+import Data.Functor.Foldable.TH (makeBaseFunctor)
+
+makeBaseFunctor ''Expr
+
+freeVars :: Expr -> Set String
+freeVars = cata go
+ where
+ go :: ExprF (Set String) -> Set String
+ go (VarF name) = Set.singleton name
+ go (LamF name bodyNames) = Set.difference bodyNames (Set.singleton name)
+ go fNames = foldr Set.union Set.empty fNames
+```
+
+The `makeBaseFunctor` line uses Template Haskell to generate our `ExprF`
datatype, a single layer of the `Expr` datatype. `makeBaseFunctor` also
generates instances which are useful when using recursion-schemes. For example,
we make use of the `Foldable ExprF` instance on the last line of `go`. This
`Foldable` instance exists because `ExprF` has kind `* -> *`, while `Expr` has
kind `*`.
+
+## Other recursion-schemes
+
+All of our examples so far have used `cata`. There are many more
recursion-schemes. Here is an example which follows a different recursive
structure:
+
+```haskell
+-- |
+-- >>> halves 256
+-- [256,128,64,32,16,8,4,2,1]
+halves :: Int -> [Int]
+halves 0 = []
+halves n = n : halves (n `div` 2)
+```
+
+That recursive structure is captured by the
[`ana`](https://hackage.haskell.org/package/recursion-schemes/docs/Data-Functor-Foldable.html#v:ana)
recursion-scheme:
+
+```haskell
+halves :: Int -> [Int]
+halves = ana go
+ where
+ go :: Int -> ListF Int Int
+ go 0 = Nil
+ go n = Cons n (n `div` 2)
+```
+
+The
[Data.Functor.Foldable](https://hackage.haskell.org/package/recursion-schemes/docs/Data-Functor-Foldable.html)
module provides many more.
+
+## Contributing
-Please feel free to contact us by opening a github issue or by hopping onto
the #haskell IRC channel on irc.freenode.net.
+Contributions and [bug
reports](https://github.com/ekmett/recursion-schemes/issues/new) are welcome!
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/recursion-schemes-5.2.1/Setup.hs
new/recursion-schemes-5.2.2/Setup.hs
--- old/recursion-schemes-5.2.1/Setup.hs 1970-01-01 01:00:00.000000000
+0100
+++ new/recursion-schemes-5.2.2/Setup.hs 2001-09-09 03:46:40.000000000
+0200
@@ -0,0 +1,7 @@
+module Main where
+
+import Distribution.Extra.Doctest (defaultMainWithDoctests)
+
+main :: IO ()
+main = defaultMainWithDoctests "doctests"
+
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/recursion-schemes-5.2.1/Setup.lhs
new/recursion-schemes-5.2.2/Setup.lhs
--- old/recursion-schemes-5.2.1/Setup.lhs 2001-09-09 03:46:40.000000000
+0200
+++ new/recursion-schemes-5.2.2/Setup.lhs 1970-01-01 01:00:00.000000000
+0100
@@ -1,7 +0,0 @@
-#!/usr/bin/runhaskell
-> module Main (main) where
-
-> import Distribution.Simple
-
-> main :: IO ()
-> main = defaultMain
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/recursion-schemes-5.2.1/recursion-schemes.cabal
new/recursion-schemes-5.2.2/recursion-schemes.cabal
--- old/recursion-schemes-5.2.1/recursion-schemes.cabal 2001-09-09
03:46:40.000000000 +0200
+++ new/recursion-schemes-5.2.2/recursion-schemes.cabal 2001-09-09
03:46:40.000000000 +0200
@@ -1,13 +1,13 @@
name: recursion-schemes
category: Control, Recursion
-version: 5.2.1
+version: 5.2.2
license: BSD2
cabal-version: >= 1.10
license-file: LICENSE
author: Edward A. Kmett
maintainer: "Samuel G??lineau" <[email protected]>,
- "Oleg Grenrus" <[email protected]>,
- "Ryan Scott" <[email protected]>
+ "Ryan Scott" <[email protected]>,
+ "Luc Tielen" <[email protected]>
stability: provisional
homepage: http://github.com/ekmett/recursion-schemes/
bug-reports: http://github.com/ekmett/recursion-schemes/issues
@@ -18,7 +18,7 @@
tested-with: GHC==7.4.2, GHC==7.6.3, GHC==7.8.4, GHC==7.10.3, GHC==8.0.2,
GHC==8.2.2, GHC==8.4.4, GHC==8.6.5, GHC==8.8.3, GHC==8.10.1
build-type: Simple
-extra-source-files: .travis.yml CHANGELOG.markdown .gitignore README.markdown
include/recursion-schemes-common.h
+extra-source-files: CHANGELOG.markdown .gitignore README.markdown
include/recursion-schemes-common.h
source-repository head
type: git
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/recursion-schemes-5.2.1/src/Data/Functor/Foldable/TH.hs
new/recursion-schemes-5.2.2/src/Data/Functor/Foldable/TH.hs
--- old/recursion-schemes-5.2.1/src/Data/Functor/Foldable/TH.hs 2001-09-09
03:46:40.000000000 +0200
+++ new/recursion-schemes-5.2.2/src/Data/Functor/Foldable/TH.hs 2001-09-09
03:46:40.000000000 +0200
@@ -106,14 +106,12 @@
--
-- Some doctests:
--
--- >>> data Expr a = Lit a | Add (Expr a) (Expr a) | Expr a :* [Expr a]
--- >>> ; makeBaseFunctor ''Expr
+-- >>> data Expr a = Lit a | Add (Expr a) (Expr a) | Expr a :* [Expr a];
makeBaseFunctor ''Expr
--
-- >>> :t AddF
-- AddF :: r -> r -> ExprF a r
--
--- >>> data Rose f a = Rose a (f (Rose f a))
--- >>> ; makeBaseFunctor [d| instance Functor f => Recursive (Rose f a) |]
+-- >>> data Rose f a = Rose a (f (Rose f a)); makeBaseFunctor [d| instance
Functor f => Recursive (Rose f a) |]
--
-- >>> :t RoseF
-- RoseF :: a -> f r -> RoseF f a r
@@ -264,6 +262,11 @@
<$> cons'
-- Data definition
+#if MIN_VERSION_template_haskell(2,12,0)
+ derivStrat <- do
+ e <- isExtEnabled DerivingStrategies
+ pure $ if e then Just StockStrategy else Nothing
+#endif
let dataDec = case consF of
#if MIN_VERSION_template_haskell(2,11,0)
[conF] | isNewtype ->
@@ -279,7 +282,7 @@
where
deriveds =
#if MIN_VERSION_template_haskell(2,12,0)
- [DerivClause Nothing
+ [DerivClause derivStrat
[ ConT functorTypeName
, ConT foldableTypeName
, ConT traversableTypeName ]]
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/recursion-schemes-5.2.1/src/Data/Functor/Foldable.hs
new/recursion-schemes-5.2.2/src/Data/Functor/Foldable.hs
--- old/recursion-schemes-5.2.1/src/Data/Functor/Foldable.hs 2001-09-09
03:46:40.000000000 +0200
+++ new/recursion-schemes-5.2.2/src/Data/Functor/Foldable.hs 2001-09-09
03:46:40.000000000 +0200
@@ -18,7 +18,7 @@
-- License : BSD-style (see the file LICENSE)
--
-- Maintainer : "Samuel G??lineau" <[email protected]>,
--- "Oleg Grenrus" <[email protected]>,
+-- "Luc Tielen" <[email protected]>,
-- "Ryan Scott" <[email protected]>
-- Stability : experimental
-- Portability : non-portable
@@ -26,69 +26,85 @@
----------------------------------------------------------------------------
module Data.Functor.Foldable
(
- -- * Base functors for fixed points
+ -- * Base functors
Base
, ListF(..)
- -- * Folding
- , Recursive(..)
- -- ** Combinators
- , gapo
- , gcata
- , zygo
- , gzygo
+ -- * Type classes
+ , Recursive(project)
+ , Corecursive(embed)
+ -- * Folding functions
+ -- $foldingFunctions
+ , fold
+ , cata
+ , cataA
+ , para
, histo
- , ghisto
+ , zygo
+ -- * Unfolding functions
+ , unfold
+ , ana
+ , apo
, futu
- , gfutu
+ -- * Combining unfolds and folds
+ , refold
+ , hylo
, chrono
+ -- * Changing representation
+ , refix
+ , hoist
+ , transverse
+ , cotransverse
+ -- * Advanced usage
+ -- ** Mendler-style recursion-schemes
+ , mcata
+ , mpara
+ , mhisto
+ , mzygo
+ , mana
+ , mapo
+ , mfutu
+ -- ** Fokkinga's recursion-schemes
+ , prepro
+ , postpro
+ -- ** Elgot (co)algebras
+ , elgot
+ , coelgot
+ -- ** Generalized recursion-schemes
+ , gfold
+ , gcata
+ , gpara
+ , ghisto
+ , gzygo
+ , gunfold
+ , gana
+ , gapo
+ , gfutu
+ , grefold
+ , ghylo
, gchrono
- -- ** Distributive laws
+ , gprepro
+ , gpostpro
, distCata
, distPara
, distParaT
- , distZygo
- , distZygoT
, distHisto
, distGHisto
- , distFutu
- , distGFutu
- -- * Unfolding
- , Corecursive(..)
- -- ** Combinators
- , gana
- -- ** Distributive laws
+ , distZygo
+ , distZygoT
, distAna
, distApo
, distGApo
, distGApoT
- -- * Refolding
- , hylo
- , ghylo
- -- ** Changing representation
- , hoist
- , refix
- -- * Common names
- , fold, gfold
- , unfold, gunfold
- , refold, grefold
- -- * Mendler-style
- , mcata
- , mhisto
- -- * Elgot (co)algebras
- , elgot
- , coelgot
- -- * Zygohistomorphic prepromorphisms
+ , distFutu
+ , distGFutu
+ -- ** Zygohistomorphic prepromorphisms
, zygoHistoPrepro
- -- * Effectful combinators
- , cataA
- , transverse
- , cotransverse
) where
import Control.Applicative
import Control.Comonad
import Control.Comonad.Trans.Class
-import Control.Comonad.Trans.Env
+import Control.Comonad.Trans.Env (EnvT(..))
import qualified Control.Comonad.Cofree as Cofree
import Control.Comonad.Cofree (Cofree(..))
import Control.Comonad.Trans.Cofree (CofreeF, CofreeT(..))
@@ -119,13 +135,42 @@
-- $setup
-- >>> :set -XDeriveFunctor -XScopedTypeVariables -XLambdaCase -XGADTs
-XFlexibleContexts
+-- >>> import Control.Applicative (Const (..), Applicative (..))
-- >>> import Control.Monad (void)
+-- >>> import Control.Monad.Trans.Reader (Reader, ask, local, runReader)
-- >>> import Data.Char (toUpper)
+-- >>> import Data.Fix (Fix (..))
-- >>> import Data.Foldable (traverse_)
--- >>> import Data.List (partition)
+-- >>> import Data.List (intercalate, partition)
+-- >>> import Data.List.NonEmpty (NonEmpty (..))
-- >>> import Data.Maybe (maybeToList)
+-- >>> import Data.Tree (Tree (..), drawTree)
+--
+-- >>> import Data.Functor.Base
--
-- >>> let showTree = putStrLn . go where go (Node x xs) = if null xs then x
else "(" ++ unwords (x : map go xs) ++ ")"
+--
+-- >>> let myTree = Node 0 [Node 1 [], Node 2 [], Node 3 [Node 31 [Node 311
[Node 3111 [], Node 3112 []]]]]
+
+-- $foldingFunctions
+-- Folding functions allow you to reduce a recursive structure down to a
value. The value can be a simple type such as 'Int' or 'String', or it can also
be a recursive structure. Each of the functions below will be accompanied by an
example which folds the following @Tree Int@ down to some 'String'.
+--
+-- >>> putStr $ drawTree $ fmap show myTree
+-- 0
+-- |
+-- +- 1
+-- |
+-- +- 2
+-- |
+-- `- 3
+-- |
+-- `- 31
+-- |
+-- `- 311
+-- |
+-- +- 3111
+-- |
+-- `- 3112
-- | Obtain the base functor for a recursive datatype.
--
@@ -165,27 +210,83 @@
project = to . gcoerce . from
#endif
- -- | A generalization of 'foldr'. The elements of the base functor, called
the
- -- "recursive positions", give the result of folding the sub-tree at that
- -- position.
+ -- | An alias for 'fold'.
--
- -- >>> :{
- -- >>> let oursum = cata $ \case
- -- >>> Nil -> 0
- -- >>> Cons x acc -> x + acc
- -- >>> :}
- --
- -- >>> oursum [1,2,3]
- -- 6
- --
- cata :: (Base t a -> a) -- ^ a (Base t)-algebra
- -> t -- ^ fixed point
- -> a -- ^ result
+ -- 'fold' is by far the most common recursion-scheme, because working one
layer at a time is the most common strategy for writing a recursive function.
But there are also other, rarer strategies. Researchers have given names to the
most common strategies, and their name for 'fold' is "catamorphism". They also
give its @Base t a -> a@ argument a special name, "(@Base t@)-algebra". More
generally, a function of the form @f a -> a@ is called an "f-algebra".
+ --
+ -- The names might seem intimidating at first, but using the standard
nomenclature has benefits. If you program with others, it can be useful to have
a shared vocabulary to refer to those recursion patterns. For example, you can
discuss which type of recursion is the most appropriate for the problem at
hand. Names can also help to structure your thoughts while writing recursive
functions.
+ --
+ -- The rest of this module lists a few of the other recursion-schemes which
are common enough to have a name. In this section, we restrict our attention to
those which fold a recursive structure down to a value. In the examples all
functions will be of type @Tree Int -> String@.
+ cata :: (Base t a -> a) -> t -> a
cata f = c where c = f . fmap c . project
-- | A variant of 'cata' in which recursive positions also include the
-- original sub-tree, in addition to the result of folding that sub-tree.
--
+ -- For our running example, let's add a number to each node indicating how
+ -- many children are below it. To do so, we will need to count those nodes
+ -- from the original sub-tree.
+ --
+ -- >>> :{
+ -- let pprint4 :: Tree Int -> String
+ -- pprint4 = flip runReader 0 . para go
+ -- where
+ -- go :: TreeF Int (Tree Int, Reader Int String)
+ -- -> Reader Int String
+ -- go (NodeF i trss) = do
+ -- -- trss :: [(Tree Int, Reader Int String)]
+ -- -- ts :: [Tree Int]
+ -- -- rss :: [Reader Int String]
+ -- -- ss :: [String]
+ -- let (ts, rss) = unzip trss
+ -- let count = sum $ fmap length ts
+ -- ss <- local (+ 2) $ sequence rss
+ -- indent <- ask
+ -- let s = replicate indent ' '
+ -- ++ "* " ++ show i
+ -- ++ " (" ++ show count ++ ")"
+ -- pure $ intercalate "\n" (s : ss)
+ -- :}
+ --
+ -- >>> putStrLn $ pprint4 myTree
+ -- * 0 (7)
+ -- * 1 (0)
+ -- * 2 (0)
+ -- * 3 (4)
+ -- * 31 (3)
+ -- * 311 (2)
+ -- * 3111 (0)
+ -- * 3112 (0)
+ --
+ -- One common use for 'para' is to construct a new tree which reuses most of
+ -- the sub-trees from the original. In the following example, we insert a new
+ -- node under the leftmost leaf. This requires allocating new nodes along a
+ -- path from the root to that leaf, while keeping every other sub-tree
+ -- untouched.
+ --
+ -- >>> :{
+ -- let insertLeftmost :: Int -> Tree Int -> Tree Int
+ -- insertLeftmost new = para go
+ -- where
+ -- go :: TreeF Int (Tree Int, Tree Int)
+ -- -> Tree Int
+ -- go (NodeF i []) = Node i [Node new []]
+ -- go (NodeF i ((_orig, recur) : tts)) =
+ -- -- tts :: [(Tree Int, Tree Int)]
+ -- let (origs, _recurs) = unzip tts
+ -- in Node i (recur : origs)
+ -- :}
+ --
+ -- >>> putStrLn $ pprint4 $ insertLeftmost 999 myTree
+ -- * 0 (8)
+ -- * 1 (1)
+ -- * 999 (0)
+ -- * 2 (0)
+ -- * 3 (4)
+ -- * 31 (3)
+ -- * 311 (2)
+ -- * 3111 (0)
+ -- * 3112 (0)
para :: (Base t (t, a) -> a) -> t -> a
para t = p where p x = t . fmap ((,) <*> p) $ project x
@@ -237,19 +338,7 @@
embed = to . gcoerce . from
#endif
- -- | A generalization of 'unfoldr'. The starting seed is expanded into a base
- -- functor whose recursive positions contain more seeds, which are themselves
- -- expanded, and so on.
- --
- -- >>> :{
- -- >>> let ourEnumFromTo :: Int -> Int -> [Int]
- -- >>> ourEnumFromTo lo hi = ana go lo where
- -- >>> go i = if i > hi then Nil else Cons i (i + 1)
- -- >>> :}
- --
- -- >>> ourEnumFromTo 1 4
- -- [1,2,3,4]
- --
+ -- | An alias for 'unfold'.
ana
:: (a -> Base t a) -- ^ a (Base t)-coalgebra
-> a -- ^ seed
@@ -278,7 +367,54 @@
-> t
gpostpro k e g = a . return where a = embed . fmap (hoist e . a . join) . k
. liftM g
--- | An optimized version of @cata f . ana g@.
+-- | An alias for 'refold'.
+hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
+hylo f g = h where h = f . fmap h . g
+
+-- | Folds a recursive type down to a value, one layer at a time.
+--
+-- >>> :{
+-- let mySum :: [Int] -> Int
+-- mySum = fold $ \case
+-- Nil -> 0
+-- Cons x sumXs -> x + sumXs
+-- :}
+--
+-- >>> mySum [10,11,12]
+-- 33
+--
+-- In our running example, one layer consists of an 'Int' and a list of
recursive positions. In @Tree Int@, those recursive positions contain sub-trees
of type @Tree Int@. Since we are working one layer at a time, the @Base t a ->
a@ function is not given a @Tree Int@, but a @TreeF Int String@. That is, each
recursive position contains the 'String' resulting from recursively folding the
corresponding sub-tree.
+--
+-- >>> :{
+-- let pprint1 :: Tree Int -> String
+-- pprint1 = fold $ \case
+-- NodeF i [] -> show i
+-- NodeF i ss -> show i ++ ": [" ++ intercalate ", " ss ++ "]"
+-- :}
+--
+-- >>> putStrLn $ pprint1 myTree
+-- 0: [1, 2, 3: [31: [311: [3111, 3112]]]]
+--
+-- More generally, the 't' argument is the recursive value, the 'a' is the
final result, and the @Base t a -> a@ function explains how to reduce a single
layer full of recursive results down to a result.
+fold :: Recursive t => (Base t a -> a) -> t -> a
+fold = cata
+
+-- | A generalization of 'unfoldr'. The starting seed is expanded into a base
+-- functor whose recursive positions contain more seeds, which are themselves
+-- expanded, and so on.
+--
+-- >>> :{
+-- >>> let ourEnumFromTo :: Int -> Int -> [Int]
+-- >>> ourEnumFromTo lo hi = ana go lo where
+-- >>> go i = if i > hi then Nil else Cons i (i + 1)
+-- >>> :}
+--
+-- >>> ourEnumFromTo 1 4
+-- [1,2,3,4]
+unfold :: Corecursive t => (a -> Base t a) -> a -> t
+unfold = ana
+
+-- | An optimized version of @fold f . unfold g@.
--
-- Useful when your recursion structure is shaped like a particular recursive
-- datatype, but you're neither consuming nor producing that recursive
datatype.
@@ -289,7 +425,7 @@
--
-- >>> :{
-- >>> let quicksort :: Ord a => [a] -> [a]
--- >>> quicksort = hylo merge split where
+-- >>> quicksort = refold merge split where
-- >>> split [] = Tip
-- >>> split (x:xs) = let (l, r) = partition (<x) xs in Branch l x r
-- >>>
@@ -299,19 +435,6 @@
--
-- >>> quicksort [1,5,2,8,4,9,8]
-- [1,2,4,5,8,8,9]
---
-hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
-hylo f g = h where h = f . fmap h . g
-
--- | An alias for 'cata'.
-fold :: Recursive t => (Base t a -> a) -> t -> a
-fold = cata
-
--- | An alias for 'ana'.
-unfold :: Corecursive t => (a -> Base t a) -> a -> t
-unfold = ana
-
--- | An alias for 'hylo'.
refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
refold = hylo
@@ -530,6 +653,7 @@
embed (CMTF.Pure a) = CMFC.F $ \p _ -> p a
embed (CMTF.Free fr) = CMFC.F $ \p f -> f $ fmap (cmfcCata p f) fr
+-- TODO: link from 'para' to 'zygo'
zygo :: Recursive t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a
zygo f = gfold (distZygo f)
@@ -598,11 +722,41 @@
-- | Mendler-style iteration
mcata :: (forall y. (y -> c) -> f y -> c) -> Fix f -> c
-mcata psi = psi (mcata psi) . unFix
+mcata psi = c where c = psi c . unFix
+
+-- | Mendler-style recursion
+--
+-- @since 5.2.2
+mpara :: (forall y. (y -> c) -> (y -> Fix f) -> f y -> c) -> Fix f -> c
+mpara psi = c where c = psi c id . unFix
+
+-- | Mendler-style semi-mutual recursion
+--
+-- @since 5.2.2
+mzygo :: (forall y. (y -> b) -> f y -> b) -> (forall y. (y -> c) -> (y -> b)
-> f y -> c) -> Fix f -> c
+mzygo phi psi = c where c = psi c (mcata phi) . unFix
-- | Mendler-style course-of-value iteration
mhisto :: (forall y. (y -> c) -> (y -> f y) -> f y -> c) -> Fix f -> c
-mhisto psi = psi (mhisto psi) unFix . unFix
+mhisto psi = c where c = psi c unFix . unFix
+
+-- | Mendler-style coiteration
+--
+-- @since 5.2.2
+mana :: (forall y. (x -> y) -> x -> f y) -> x -> Fix f
+mana phi = c where c = Fix . phi c
+
+-- | Mendler-style corecursion
+--
+-- @since 5.2.2
+mapo :: (forall y. (Fix f -> y) -> (x -> y) -> x -> f y) -> x -> Fix f
+mapo phi = c where c = Fix . phi id c
+
+-- | Mendler-style course-of-values coiteration
+--
+-- @since 5.2.2
+mfutu :: (forall y. (f y -> y) -> (x -> y) -> x -> f y) -> x -> Fix f
+mfutu phi = c where c = Fix . phi Fix c
-- | Elgot algebras
elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a
@@ -628,15 +782,79 @@
-- Effectful combinators
-------------------------------------------------------------------------------
--- | Effectful 'fold'.
+-- | A specialization of 'cata' for effectful folds.
--
--- This is a type specialisation of 'cata'.
+-- 'cataA' is the same as 'cata', but with a more specialized type. The only
+-- reason it exists is to make it easier to discover how to use this library
+-- with effects.
+--
+-- For our running example, let's improve the output format of our
+-- pretty-printer by using indentation. To do so, we will need to keep track of
+-- the current indentation level. We will do so using a @Reader Int@ effect.
+-- Our recursive positions will thus contain @Reader Int String@ actions, not
+-- @String@s. This means we need to run those actions in order to get the
+-- results.
--
--- An example terminating a recursion immediately:
---
--- >>> cataA (\alg -> case alg of { Nil -> pure (); Cons a _ -> Const [a] })
"hello"
--- Const "h"
+-- >>> :{
+-- let pprint2 :: Tree Int -> String
+-- pprint2 = flip runReader 0 . cataA go
+-- where
+-- go :: TreeF Int (Reader Int String)
+-- -> Reader Int String
+-- go (NodeF i rss) = do
+-- -- rss :: [Reader Int String]
+-- -- ss :: [String]
+-- ss <- local (+ 2) $ sequence rss
+-- indent <- ask
+-- let s = replicate indent ' ' ++ "* " ++ show i
+-- pure $ intercalate "\n" (s : ss)
+-- :}
+--
+-- >>> putStrLn $ pprint2 myTree
+-- * 0
+-- * 1
+-- * 2
+-- * 3
+-- * 31
+-- * 311
+-- * 3111
+-- * 3112
+--
+-- The fact that the recursive positions contain 'Reader' actions instead of
+-- 'String's gives us some flexibility. Here, we are able to increase the
+-- indentation by running those actions inside a 'local' block. More generally,
+-- we can control the order of their side-effects, interleave them with other
+-- effects, etc.
+--
+-- A similar technique is to specialize 'cata' so that the result is a
+-- function. This makes it possible for data to flow down in addition to up.
+-- In this modified version of our running example, the indentation level flows
+-- down from the root to the leaves, while the resulting strings flow up from
+-- the leaves to the root.
--
+-- >>> :{
+-- let pprint3 :: Tree Int -> String
+-- pprint3 t = cataA go t 0
+-- where
+-- go :: TreeF Int (Int -> String)
+-- -> Int -> String
+-- go (NodeF i fs) indent =
+-- -- fs :: [Int -> String]
+-- let indent' = indent + 2
+-- ss = map (\f -> f indent') fs
+-- s = replicate indent ' ' ++ "* " ++ show i
+-- in intercalate "\n" (s : ss)
+-- :}
+--
+-- >>> putStrLn $ pprint3 myTree
+-- * 0
+-- * 1
+-- * 2
+-- * 3
+-- * 31
+-- * 311
+-- * 3111
+-- * 3112
cataA :: (Recursive t) => (Base t (f a) -> f a) -> t -> f a
cataA = cata
