HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

Modulefcf-containers-0.8.2Haskell2010

Fcf.Alg.List

Fcf.Alg.List

Type-level ListF to be used with Cata, Ana and Hylo.

This module also contains other list-related functions (that might move to other place some day).

To see examples, please do take a look of the respective test module.

  • 20 types
datadata ListF a b
#

Base functor for a list of type [a].

Constructors

Instances14Eval, …
datadata ListToFix (b :: [a]) (c :: Fix (ListF a))
#

ListToFix can be used to turn a normal type-level list into the base functor type ListF, to be used with e.g. Cata. For examples in use, see LenAlg and SumAlg.

Ideally, we would have one ToFix type-level function for which we could give type instances for different type-level types, like lists, trees etc. See TODO.md.

Example
:kind! Eval (ListToFix '[1,2,3])

Eval (ListToFix '[1,2,3]) :: Fix (ListF TL.Natural) = 'Fix ('ConsF 1 ('Fix ('ConsF 2 ('Fix ('ConsF 3 ('Fix 'NilF))))))

Instances2Eval
datadata LenAlg (b :: ListF a Nat) (c :: Nat)
#

Example algebra to calculate list length.

Example
:kind! Eval (Cata LenAlg =<< ListToFix '[1,2,3])

Eval (Cata LenAlg =<< ListToFix '[1,2,3]) :: TL.Natural = 3

Instances2Eval
  • type Eval (LenAlg 'NilF) = 0Defined in fcf-containers-0.8.2 · Fcf.Alg.List
  • type Eval (LenAlg ('ConsF a2 b)) = 1 + bDefined in fcf-containers-0.8.2 · Fcf.Alg.List
datadata SumAlg (a :: ListF Nat Nat) (b :: Nat)
#

Example algebra to calculate the sum of Nats in a list.

Example
:kind! Eval (Cata SumAlg =<< ListToFix '[1,2,3,4])

Eval (Cata SumAlg =<< ListToFix '[1,2,3,4]) :: TL.Natural = 10

Instances2Eval
  • type Eval (SumAlg 'NilF) = 0Defined in fcf-containers-0.8.2 · Fcf.Alg.List
  • type Eval (SumAlg ('ConsF a b)) = a + bDefined in fcf-containers-0.8.2 · Fcf.Alg.List
datadata ProdAlg (a :: ListF Nat Nat) (b :: Nat)
#

Example algebra to calculate the prod of Nats in a list.

Example
:kind! Eval (Cata ProdAlg =<< ListToFix '[1,2,3,4])

Eval (Cata ProdAlg =<< ListToFix '[1,2,3,4]) :: TL.Natural = 24

Instances2Eval
  • type Eval (ProdAlg 'NilF) = 1Defined in fcf-containers-0.8.2 · Fcf.Alg.List
  • type Eval (ProdAlg ('ConsF a b)) = a * bDefined in fcf-containers-0.8.2 · Fcf.Alg.List
datadata ListToParaFix (b :: [a]) (c :: Fix (ListF (a, [a])))
#

Form a Fix-structure that can be used with Para.

Example
:kind! Eval (ListToParaFix '[1,2,3])

Eval (ListToParaFix '[1,2,3]) :: Fix (ListF (TL.Natural, [TL.Natural])) = 'Fix ('ConsF '(1, '[2, 3]) ('Fix ('ConsF '(2, '[3]) ('Fix ('ConsF '(3, '[]) ('Fix 'NilF))))))

Instances2Eval
datadata DedupAlg (b :: ListF (a, [a]) (Fix (ListF (a, [a])), [a])) (c :: [a])
#

Example from recursion-package by Vanessa McHale.

This removes duplicates from a list (by keeping the right-most one).

Example
:kind! Eval (Para DedupAlg =<< ListToParaFix '[1,1,3,2,5,1,3,2])

Eval (Para DedupAlg =<< ListToParaFix '[1,1,3,2,5,1,3,2]) :: [TL.Natural] = '[5, 1, 3, 2]

Instances2Eval
datadata Sliding (b :: Nat) (c :: [a]) (d :: [[a]])
#

Example from Recursion Schemes by example by Tim Williams.

Example
:kind! Eval (Sliding 3 '[1,2,3,4,5,6])

Eval (Sliding 3 '[1,2,3,4,5,6]) :: [[TL.Natural]] = '[ '[1, 2, 3], '[2, 3, 4], '[3, 4, 5], '[4, 5, 6], '[5, 6], '[6]]

Instances1Eval
datadata SlidingAlg (b :: Nat) (c :: ListF (a, [a]) (Fix (ListF (a, [a])), [[a]])) (d :: [[a]])
#

Tim Williams, Recursion Schemes by example, example for Para. See Sliding-function.

Instances2Eval
datadata Evens (b :: [a]) (c :: [a])
#

This picks up the elements on even positions on a list and is an example on how to use Histo. This example is from Tim Williams, Recursion Schemes by example.

Example
:kind! Eval (Evens =<< RunInc 8)

Eval (Evens =<< RunInc 8) :: [TL.Natural] = '[2, 4, 6, 8]

Instances1Eval
datadata RunInc (a :: Nat) (b :: [Nat])
#

Construct a run (that is, a natuaral number sequence from 1 to arg).

Example
:kind! Eval (RunInc 8)

Eval (RunInc 8) :: [TL.Natural] = '[1, 2, 3, 4, 5, 6, 7, 8]

Instances1Eval
datadata Sum (a :: [Nat]) (b :: Nat)
#

Sum a Nat-list.

Example
:kind! Eval (Sum '[1,2,3])

Eval (Sum '[1,2,3]) :: TL.Natural = 6

Instances1Eval
  • type Eval (Sum ns) = Eval (Foldr (+) 0 ns)Defined in fcf-containers-0.8.2 · Fcf.Alg.List
datadata MToN (a :: Nat) (b :: Nat) (c :: [Nat])
#

Function to form Nat lists like [1..5] or [3..10]

Example
:kind! Eval (MToN 1 3)

Eval (MToN 1 3) :: [TL.Natural] = '[1, 2, 3]

Instances1Eval
datadata ToList (b :: a) (c :: [a])
#

ToList for type-level lists.

Example
:kind! Eval (ToList 1)

Eval (ToList 1) :: [TL.Natural] = '[1]

Instances1Eval
  • type Eval (ToList a) = '[a]Defined in fcf-containers-0.8.2 · Fcf.Alg.List
datadata Equal (b :: [a]) (c :: [a]) (d :: Bool)
#

Equal tests for list equality. We may change the name to (==).

Example
:kind! Eval (Equal '[1,2,3] '[1,2,3])

Eval (Equal '[1,2,3] '[1,2,3]) :: Bool = 'True

:kind! Eval (Equal '[1,2,3] '[1,3,2])

Eval (Equal '[1,2,3] '[1,3,2]) :: Bool = 'False

Instances1Eval