Skip to content

Instantly share code, notes, and snippets.

View olligobber's full-sized avatar

olligobber olligobber

35 followers · 36 following
View GitHub Profile
@olligobber
olligobber / RatPoly.hs
Last active May 8, 2018 07:42
Work with Polynomials of Rational Coefficients
module RatPoly
( RatPoly(Constant)
, x
, (//)
, degree
, eval
, polyDivMod
, polyDiv
, polyMod
, polyGcd
@olligobber
olligobber / QuantumBogoSort.hs
Created May 10, 2018 11:04
Abuses Haskell Monads to simulate Quantum BogoSort.
module QuantumBogoSort (sort, sortBy) where
import Data.List (permutations)
import Control.Monad (guard)
-- Check if a list is sorted
sortedBy :: (a -> a -> Ordering) -> [a] -> Bool
sortedBy _ [] = True
sortedBy _ [_] = True
sortedBy c (x:y:xs) = c x y <= EQ && sortedBy c (y:xs)
@olligobber
olligobber / Poly.hs
Last active July 12, 2018 02:26
Work with Polynomials over Arbitrary Fields
module Poly (Field, inverse, (//), Poly(C), x, degree, leading, polyDivMod,
polyDiv, polyMod, polyGcd, polyGcdW) where
import Control.Monad.Trans.Writer (Writer, tell)
-- Typeclass for Algebraic Fields
class Num a => Field a where
(//) :: a -> a -> a
a // b = a * inverse b
inverse :: a -> a
@olligobber
olligobber / VanEck.hs
Created June 11, 2019 14:17
Generate and print the entire Van Eck sequence
import qualified Data.Map.Lazy as Map
import Data.Map.Lazy (Map)
import Data.List (unfoldr)
-- Data needed to extend the sequence
data State = State {
history :: Map Integer Integer, -- When each number except the current was seen
position :: Integer, -- Current position
curr :: Integer -- Current value
}
@olligobber
olligobber / log.txt
Last active June 29, 2019 19:29
Inspired by https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF
> let proplist = ((\x -> conj (prop $ 'a':show x) (prop $ 'b':show x)) <$> [0..2])
> putStr . unlines $ fancyRender id <$> proplist
a0 ∧ b0
a1 ∧ b1
a2 ∧ b2
> putStrLn $ fancyRender (either (('t':).show) id) $ disjSmall proplist
(¬t0 ∨ a0) ∧ (¬t0 ∨ b0) ∧ (¬t1 ∨ a1) ∧ (¬t1 ∨ b1) ∧ (¬t2 ∨ a2) ∧ (¬t2 ∨ b2) ∧ (t0 ∨ t1 ∨ t2)
> putStrLn $ fancyRender id $ foldl1 disjBig proplist
(a0 ∨ a1 ∨ a2) ∧ (a0 ∨ a1 ∨ b2) ∧ (a0 ∨ a2 ∨ b1) ∧ (a0 ∨ b1 ∨ b2) ∧ (a1 ∨ a2 ∨ b0) ∧ (a1 ∨ b0 ∨ b2) ∧ (a2 ∨ b0 ∨ b1) ∧ (b0 ∨ b1 ∨ b2)
@olligobber
olligobber / UnionFind.hs
Last active September 19, 2019 09:13
An implementation of a disjoint set data structure (aka unionfind) in Haskell
{-# LANGUAGE RankNTypes #-}
module UnionFind (
Getter,
Setter,
UnionFind,
UnionFindS,
new,
find,
union,
@olligobber
olligobber / order.bf
Last active November 18, 2019 12:39
Given a stream of bytes as input, each pair is ordered so the smallest is output first and the largest is output second. Uses 6 bytes of memory.
LOOP FOREVER
+[-
LOAD FIRST INPUT IN POS 0 & SECOND IN POS 1
,>,<
WHILE POS 0 ISNT 0
[
MOVE TO POS 1 & COPY VALUE TO POS 3 & 4
>[->>+>+>+<<<<]>>>>[-<<<<+>>>>]<<<<
MOVE TO POS 3
>>
@olligobber
olligobber / sort.bf
Last active April 9, 2020 08:12
Given a 0-terminated list of bytes, outputs them in increasing order. Uses 2n+4 bytes of memory to sort n bytes of input, using insertion sort.
WHILE INPUT IS NONZERO
,[
MOVE TO LEFT ELEMENT
<<
WHILE LEFT ELEMENT EXISTS
[
ORDER POS 0 AND POS 2 WITH SMALLEST ON RIGHT
USING POS 0 & 1 & 2 & 3 & 5 & 7
WHILE POS 0 ISNT 0
@olligobber
olligobber / primes.bf
Created November 25, 2019 11:37
Outputs all 1 byte primes using only 7 bytes of memory.
SET POS 0 TO 2
++
WHILE POS 0 ISNT 0
[
SET POS 1 TO 2
>++<
SET POS 2 TO POS 0 MINUS POS 1
[->>+>+<<<]>>>[-<<<+>>>]<<[->->+<<]>>[-<<+>>]<<<
WHILE POS 1 ISNT POS 0 (POS 2 ISNT 0)
>>[<<
@olligobber
olligobber / Rates.hs
Last active January 12, 2020 04:11
Use of Haskell's type checker for calculations of rates
{-# LANGUAGE TypeOperators, ExplicitNamespaces #-}
module Rates (
Rate(..),
(&*),
rev,
(&/),
RatRate,
type (//)
) where