Church-encoded lists for constant-space enumeration (experimental)

Enumeration.hs

{-# LANGUAGE RankNTypes, LambdaCase, BlockArguments #-}

module Enumeration (
  Enumeration(..),
  fromFoldable,
) where

-- GHC/base
import GHC.Exts (build)
-- base
import Data.Function (on)
import Data.Foldable (Foldable(toList))
import Control.Applicative (Alternative(..))


newtype Enumeration a = MkEnumeration{
  unMkEnumeration :: forall r. (a -> r -> r) -> r -> r
} deriving Functor

instance Applicative Enumeration where
  {-# INLINE pure #-}
  pure x = MkEnumeration \cons nil -> cons x nil
  {-# INLINE liftA2 #-}
  liftA2 f xs ys = MkEnumeration \cons nil ->
    unMkEnumeration xs (\x -> unMkEnumeration ys (cons . f x)) nil

instance Alternative Enumeration where
  empty = MkEnumeration \_ nil -> nil
  xs <|> ys = MkEnumeration \cons nil ->
    unMkEnumeration xs cons (unMkEnumeration ys cons nil)

instance Monad Enumeration where
  xs >>= k = MkEnumeration \cons nil ->
    unMkEnumeration xs (\x -> unMkEnumeration (k x) cons) nil

instance Foldable Enumeration where
  {-# INLINE foldr #-}
  foldr f z xs = unMkEnumeration xs f z
  {-# INLINE toList #-}
  toList xs = build (unMkEnumeration xs)

fromFoldable :: Foldable f => f a -> Enumeration a
fromFoldable xs = MkEnumeration \cons nil -> foldr cons nil xs