Skip to content

Instantly share code, notes, and snippets.

View AndrasKovacs's full-sized avatar

András Kovács AndrasKovacs

View GitHub Profile
@AndrasKovacs
AndrasKovacs / TuringMachine.hs
Last active December 17, 2015 09:59
Turing machine.
import Data.Map ((!), fromList, Map)
data Direction = L | R
type Symbol = Char
type State = Maybe Int
type Rules = Map (State, Symbol) (Symbol, Direction, State)
turingMachine :: Rules -> Symbol -> [Symbol] -> [Symbol]
turingMachine rules blank tape = let
@AndrasKovacs
AndrasKovacs / Boggle.hs
Last active December 18, 2015 17:49
Getting all words out of Boggle tables.
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as UV
import qualified Data.ByteString.Char8 as B
import Data.Ix
import Text.Printf
import Data.List
import Data.Ord
import System.Environment
@AndrasKovacs
AndrasKovacs / NatInduction.agda
Last active December 24, 2015 08:19
Minimal agda definition for induction on natural numbers. (I realize that it's actually just dependent foldr).
module NatInduction where
data ℕ : Set where
zero : ℕ
suc : ℕ → ℕ
ℕ-ind : (prop : ℕ → Set)
→ (zero_proof : prop zero)
→ (ind_hyp : ∀ n → prop n → prop (suc n))
→ (n : ℕ)
@AndrasKovacs
AndrasKovacs / Brainfuck.hs
Last active December 24, 2015 20:19
Brainfuck interpreter. Usage: just run script or executable with Brainfuck source file as commandline argument.It has bidirectionally "infinite" memory and one-byte cells.
import System.Environment
import Data.Word
import Data.Char
import Control.Arrow
import Data.Function
infixr 5 :>
data Mem = {- UNPACK -} !Word8 :> Mem
eval :: Mem -> Mem -> String -> IO (Mem, Mem)
@AndrasKovacs
AndrasKovacs / bf2c.hs
Last active December 24, 2015 23:59
Moderately optimizing brainfuck-to-C compiler.
{-# LANGUAGE LambdaCase #-}
import qualified Data.Attoparsec.Text as P
import qualified Data.Text as T
import qualified Data.Text.IO as TIO
import Control.Applicative
import Data.Char
import Data.List
import Data.Word
@AndrasKovacs
AndrasKovacs / Huffman.hs
Last active December 25, 2015 08:39
Huffman code generation.
{-# LANGUAGE LambdaCase #-}
import qualified Data.PQueue.Min as Q
import Control.Arrow
import Data.Function
data Tree
= Empty
| Leaf {weight :: Double}
| Node {weight :: Double, _left, _right :: Tree}
@AndrasKovacs
AndrasKovacs / ChurchNum.hs
Created October 12, 2013 10:02
Church numerals.
{-# LANGUAGE RankNTypes, TypeSynonymInstances, FlexibleInstances #-}
type ChNat a = (a -> a) -> a -> a
generalize :: ChNat Int -> (forall a. ChNat a)
generalize n = foldr (.) id . replicate (fromEnum n)
instance Num (ChNat Int) where
fromInteger = toEnum . fromIntegral
a + b = \f -> a f . b f
@AndrasKovacs
AndrasKovacs / Goto.hs
Created October 12, 2013 10:52
Backwards goto and looping via the continuation monad.
import Control.Monad.Cont
import Data.Function
getLabel = ContT fix
goto label = lift label
getLoop x = ContT (\k -> let f x' = ContT (\_ -> k (f, x')) in k (f, x))
gotoTest :: IO ()
@AndrasKovacs
AndrasKovacs / NatProps.agda
Last active December 26, 2015 03:29
Some basic properties of natural numbers in Agda.
module NatProps where
open import Relation.Binary.PropositionalEquality
open import Relation.Nullary
open import Data.Sum
open import Function
data ℕ : Set where
zero : ℕ
suc : ℕ → ℕ
@AndrasKovacs
AndrasKovacs / Sort.hs
Last active December 27, 2015 00:09
Investigating whether Data.List.sort gets faster when we replace the DList usage with plain reversing.
import qualified Criterion.Main as Crit
import qualified Test.Tasty.QuickCheck as QC
import qualified Test.Tasty as Tasty
import Data.List
import Data.List.Split
import System.Random