Josh Ko josh-hs-ko

yangzhixuan / FastApp.hs

Last active February 14, 2025 13:09

Efficient Free Applicatives/Monads from Okasaki's Functional Data Structures, with an application to fast substitution-based lambda normalising

	{-# LANGUAGE GADTs, RankNTypes, TypeOperators, ScopedTypeVariables, KindSignatures #-}

	module FastApp where

	import Prelude hiding (head, tail)
	import Control.Applicative

	-- Chris Okasaki invented many cool and efficient functional data structures
	-- in his book Purely Functional Data Structures.
	-- Among them, one is catenable lists supporting amortised O(1)-time \|(++)\|,