-
-
Save hardentoo/1eb0c6734eccef4d424e7675109789d7 to your computer and use it in GitHub Desktop.
Time-traveling recursion schemes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{-# LANGUAGE LambdaCase #-} | |
{-# LANGUAGE TypeFamilies #-} | |
import Control.Comonad.Cofree | |
import Control.Monad.Free | |
import Data.Functor.Foldable | |
oddIndices :: [a] -> [a] | |
oddIndices = histo $ \case | |
Nil -> [] | |
Cons h (_ :< Nil) -> [h] | |
Cons h (_ :< Cons _ (t :< _)) -> h:t | |
evenIndices :: [a] -> [a] | |
evenIndices = histo $ \case | |
Nil -> [] | |
Cons _ (_ :< Nil) -> [] | |
Cons _ (_ :< Cons h (t :< _)) -> h:t | |
oddIndicesF :: [a] -> [a] | |
oddIndicesF = futu coalg where | |
coalg list = case project list of | |
Nil -> Nil | |
Cons x s -> Cons x $ do | |
return $ case project s of | |
Nil -> s | |
Cons _ t -> t | |
evenIndicesF :: [a] -> [a] | |
evenIndicesF = futu coalg where | |
coalg list = case project list of | |
Nil -> Nil | |
Cons _ s -> case project s of | |
Nil -> Nil | |
Cons h t -> Cons h $ return t | |
nil :: Free (Prim [a]) b | |
nil = liftF Nil | |
cons :: a -> b -> Free (Prim [a]) b | |
cons h t = liftF (Cons h t) | |
twiddle :: [a] -> [a] | |
twiddle = futu coalg where | |
coalg r = case project r of | |
Nil -> Nil | |
Cons x l -> case project l of | |
Nil -> Cons x nil | |
Cons h t -> Cons h $ cons x t |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment