benjamin-hodgson’s gists

benjamin-hodgson / heapqueue.py

Last active August 29, 2015 14:00

A wrapper of the standard library's heapq, ecapsulated as a class.

	import collections.abc
	import heapq


	class HeapQueue(collections.abc.Container, collections.abc.Sized):
	"""
	A min-heap class using the standard library's heapq module.
	This comes in handy if you need a priority-queue algorithm
	but you don't need the heavy machinery of queue.PriorityQueue
	(like blocking calls, timeouts, thread-safety, and so on).

benjamin-hodgson / boggle.hs

Last active April 8, 2020 21:46

Boggle solver

	{-# LANGUAGE DeriveFoldable #-}
	{-# LANGUAGE DeriveFunctor #-}
	{-# LANGUAGE DeriveTraversable #-}
	{-# LANGUAGE TupleSections #-}
	{-# LANGUAGE TypeOperators #-}


	import Control.Comonad
	import Control.Monad
	import Data.Functor.Reverse

benjamin-hodgson / TransformerStacks.hs

Last active February 14, 2017 00:30

	{-# LANGUAGE InstanceSigs #-}
	{-# LANGUAGE TypeOperators #-}
	{-# LANGUAGE PolyKinds #-}
	{-# LANGUAGE ScopedTypeVariables #-}


	import Control.Monad
	import Data.Constraint

benjamin-hodgson / AnnihilationClientServer.hs

Created June 29, 2017 01:40

Modelling stateful request/response processes using dual functors

	{-# LANGUAGE DeriveFunctor #-}
	{-# LANGUAGE FunctionalDependencies #-}
	{-# LANGUAGE UndecidableInstances #-}

	import Control.Monad (ap)
	import Control.Monad.Free
	import Control.Comonad
	import Control.Comonad.Cofree
	import Data.List

benjamin-hodgson / Permutations.hs

Last active May 25, 2018 14:10

	permutations :: [a] -> [[a]]
	permutations [] = [[]]
	permutations (x:xs) = concatMap (insertions x) (permutations xs)
	where
	insertions x [] = [[x]]
	insertions x zs@(y:ys) = (x:zs) : [y:ins \| ins <- insertions x ys]

benjamin-hodgson / LensWish.cs

Created March 19, 2018 16:08

Composable lens hierarchy using default interface implementations

	interface ISetter<in S, out T, out A, in B>
	{
	T Rewrite(S oldContainer, Func<A, B> rewriter);
	}

	interface IFold<in S, out A>
	{
	R Aggregate<R>(S container, R seed, Func<R, A, R> aggregator);
	}

benjamin-hodgson / EM.agda

Last active May 16, 2018 09:50

Kleisli and Eilenberg-Moore decompositions and their corresponding monad transformers

	open import Agda.Primitive

	module _ {l : Level} where
	record Category : Set (lsuc l) where
	infixr 10 _~>_
	infixr 90 _o_
	field
	Obj : Set l
	_~>_ : Obj -> Obj -> Set
	id : forall {x} -> x ~> x

benjamin-hodgson / RLE.hs

Created May 25, 2018 14:10

	import Data.Word (Word8)

	rleBytes :: [Word8] -> [Word8]
	rleBytes = concatMap (\(n, x) -> [n, x]) . break8 . rle

	rle :: Eq a => [a] -> [(Int, a)]
	rle = map len . runs
	where
	len (x, xs) = (length xs + 1, x)
	runs [] = []

benjamin-hodgson / FmapProof.hs

Last active March 1, 2019 19:53

fmap f x <*> fmap g y = (\x y -> f x (g y)) <$> x <*> y

	fmap f x <*> fmap g y
	(pure f <> x) <> (pure g <*> y) -- definition of fmap
	pure (.) <> (pure f <> x) <> pure g <> y -- composition
	pure (.) <> pure (.) <> pure f <> x <> pure g <*> y -- composition
	pure ((.) .) <> pure f <> x <> pure g <> y -- homomorphism
	pure ((.) . f) <> x <> pure g <*> y -- homomorphism
	pure ($ g) <> (pure ((.) . f) <> x) <*> y -- interchange
	pure (.) <> pure ($ g) <> pure ((.) . f) <> x <> y -- composition
	pure (($ g) .) <> pure ((.) . f) <> x <*> y -- homomorphism
	pure (($ g) . ((.) . f)) <> x <> y -- homomorphism

benjamin-hodgson / PrettierCPS.hs

Created August 8, 2024 00:56

"A Prettier Printer" in continuation passing style

	{- cabal:
	build-depends: base, lens, generic-lens
	-}

	{-# LANGUAGE DeriveGeneric #-}
	{-# LANGUAGE OverloadedLabels #-}
	{-# LANGUAGE RankNTypes #-}

	import Prelude hiding ((<>))
	import Control.Lens

	fmap f x <*> fmap g y
	(pure f <> x) <> (pure g <*> y) -- definition of fmap
	pure (.) <> (pure f <> x) <> pure g <> y -- composition
	pure (.) <> pure (.) <> pure f <> x <> pure g <*> y -- composition
	pure ((.) .) <> pure f <> x <> pure g <> y -- homomorphism
	pure ((.) . f) <> x <> pure g <*> y -- homomorphism
	pure ($ g) <> (pure ((.) . f) <> x) <*> y -- interchange
	pure (.) <> pure ($ g) <> pure ((.) . f) <> x <> y -- composition
	pure (($ g) .) <> pure ((.) . f) <> x <*> y -- homomorphism
	pure (($ g) . ((.) . f)) <> x <> y -- homomorphism

Benjamin Hodgson benjamin-hodgson