https://dl.acm.org/doi/10.1145/3236780 example with FunList

FunList.hs

{-# LANGUAGE RankNTypes, ScopedTypeVariables #-}
{-# OPTIONS_GHC -Wall #-}
module Parts where

import Data.Kind

import Control.Applicative (liftA2)
import Data.Function

-- in blogs
data FunList a b t = Done t
                   | More a (FunList a b (b -> t))
  deriving Functor

empty :: t -> FunList a b t
empty = Done

append :: (t -> s -> r) -> FunList a b t -> FunList a b s -> FunList a b r
append h (Done t)    ys = fmap (\s -> h t s) ys
append h (More x xs) ys = More x $ append (\bt s b -> h (bt b) s) xs ys

singleton :: a -> FunList a b b
singleton x = More x (Done id)

instance Applicative (FunList a b) where
    pure = empty
    liftA2 = append

funList' :: (forall f. Applicative f => (a -> f b) -> s -> f t) -> s -> FunList a b t
funList' trav s = trav singleton s

-- this doesn't use append. Should be more efficient, as function thunks are cheap.
funList :: (forall f. Applicative f => (a -> f b) -> s -> f t) -> s -> FunList a b t
funList trav s = lower (trav raise s)

-- Curried Yoneda is a free applicative,
-- to raise/lift we need a cons-like operation.
-- to lower we need a start value, usually something empty.
-- 
-- Recall how DList converts (reassociates) the expensive appends into cheap cons.
--
lower :: Curried (Yoneda (FunList a b)) t -> FunList a b t
lower (Curried f) = runYoneda
    (f (Yoneda (\g -> empty (g id))))
    id


raise :: a -> Curried (Yoneda (FunList a b)) b
raise x = Curried
    (\(Yoneda g) -> Yoneda (\f -> More x (g (\br b -> f (br b)))))

unfunList :: forall f s t a b. Applicative f => (s -> FunList a b t) -> (a -> f b) -> s -> f t
unfunList f afb s = go (f s) where
    go :: FunList a b r -> f r
    go (Done t)    = pure t
    go (More x xs) = liftA2 (&) (afb x) (go xs)

-------------------------------------------------------------------------------
-- Curried
-------------------------------------------------------------------------------

newtype Curried f a = Curried { runCurried :: forall r. f (a -> r) -> f r }

instance Functor f => Functor (Curried f) where
    fmap f (Curried g) = Curried (g . fmap (.f))
    {-# INLINE fmap #-}

instance Functor f => Applicative (Curried f) where
    pure a = Curried (fmap ($ a))
    {-# INLINE pure #-}
    Curried mf <*> Curried ma = Curried (ma . mf . fmap (.))
    {-# INLINE (<*>) #-}

liftCurried :: Applicative f => f a -> Curried f a
liftCurried fa = Curried (<*> fa)

lowerCurried :: Applicative f => Curried f a -> f a
lowerCurried (Curried f) = f (pure id)

-------------------------------------------------------------------------------
-- Yoneda
-------------------------------------------------------------------------------

newtype Yoneda f a = Yoneda { runYoneda :: forall b. (a -> b) -> f b }

liftYoneda :: Functor f => f a -> Yoneda f a
liftYoneda a = Yoneda (\f -> fmap f a)

lowerYoneda :: Yoneda f a -> f a
lowerYoneda (Yoneda f) = f id

instance Functor (Yoneda f) where
    fmap f m = Yoneda (\k -> runYoneda m (k . f))

{-
instance Applicative f => Applicative (Yoneda f) where
    pure a = Yoneda (\f -> pure (f a))
    Yoneda m <*> Yoneda n = Yoneda (\f -> m (f .) <*> n id)
-}