Demonstration of how the Hyperfunction implementation of list works.

HyperList.hs

{-# LANGUAGE BlockArguments #-}
{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE TypeOperators #-}
{-# OPTIONS_GHC -Wall -Werror -Wextra -Wno-name-shadowing #-}

module HyperList where

import Data.Function ((&))

newtype a -&> b = Hyp {invoke :: (b -&> a) -> b}

-- convenience function so you don't have to wrap the second argument go
-- `invoke` in a Hyp constructor
unroll :: (a -&> b) -> ((a -&> b) -> a) -> b
unroll fw = invoke fw . Hyp

type HyperList a = forall r. (a -> r) -&> (r -> r)

nil :: HyperList a
nil = Hyp \_ r -> r

cons :: a -> HyperList a -> HyperList a
cons a fw = Hyp \bw _ -> a & invoke bw fw

infixr 4 `cons`

foldr :: (a -> b -> b) -> b -> HyperList a -> b
foldr = loop
  where
    -- note the difference in type signature from `foldr` - we specialize `r`
    -- to `b` so we can recursively call loop
    loop :: (a -> b -> b) -> b -> ((a -> b) -&> (b -> b)) -> b
    loop f b fw = b & unroll fw \fw' a -> f a (loop f b fw')

-- |
-- Constructing a HyperList using `cons` and `nil`
--
-- See that `example` converts to the equivalent normal haskell list:
--
-- >>> HyperList.foldr (:) [] example
-- [0,1,2,3]
example :: HyperList Int
example = 0 `cons` 1 `cons` 2 `cons` 3 `cons` nil

-- |
-- What `example` evaluates to after all the `cons` applications are evaluated
--
-- See that `example'` converts to the equivalent normal haskell list:
--
-- >>> HyperList.foldr (:) [] example'
-- [0,1,2,3]
example' :: HyperList Int
example' = Hyp \bw _ ->
  0 & unroll bw \bw _ ->
    1 & unroll bw \bw _ ->
      2 & unroll bw \bw _ ->
        3 & unroll bw \_ r ->
          r