noughtmare’s gists

noughtmare / THParser.hs

Last active October 28, 2024 20:17

Using Template Haskell instead of a parser.

	import qualified Language.Haskell.TH.Syntax as TH

	data ULC = Var String \| Lam String ULC \| App ULC ULC deriving (Show, TH.Lift)

	quote :: TH.Exp -> Maybe ULC
	quote (TH.VarE v) = Just $ Var (TH.nameBase v)
	quote (TH.UnboundVarE v) = Just $ Var (TH.nameBase v)
	quote (TH.AppE x y) = App <$> quote x <*> quote y
	quote (TH.LamE vs x) = foldr (\v xs -> Lam <$> (case v of TH.VarP v' -> Just (TH.nameBase v'); _ -> Nothing) <*> xs) (quote x) vs
	quote _ = Nothing

noughtmare / LPS.hs

Created October 10, 2024 21:01

Longest palindromic substring (WIP)

	{-# LANGUAGE PatternSynonyms, ViewPatterns #-}
	{-# OPTIONS_GHC -Wall #-}
	import Data.List
	import Data.Ord

	isPalindrome :: Eq a => [a] -> Bool
	isPalindrome xs = xs == reverse xs

	lps, lps' :: Eq a => [a] -> [a]
	lps = maximumBy (comparing length) . filter isPalindrome . subsequences

noughtmare / Gram5.hs

Last active August 18, 2024 09:59

Data dependent parsing with explicit variables

	{- cabal:
	build-depends: base, recover-rtti, tasty-bench, tasty-bench-fit
	-}
	{-# LANGUAGE GHC2021, GADTs, DataKinds, LambdaCase, TypeFamilies #-}
	{-# OPTIONS_GHC -Wall #-}

	-- DATA-DEPENDENT PARSING WITH VARIABLES

	import Prelude hiding (Monad (..))
	import Data.Char (intToDigit)

noughtmare / Gram4.hs

Last active July 25, 2024 09:48

Parsing data dependent grammars based on https://www.well-typed.com/blog/2020/06/fix-ing-regular-expressions/#references

	{-# LANGUAGE GHC2021, GADTs, DataKinds #-}

	import Control.Monad (ap, (>=>), replicateM_, guard)
	import Control.Applicative
	import Prelude hiding (or)
	import Data.Kind
	import Data.Char

	asumMap :: Alternative f => (a -> f b) -> [a] -> f b
	asumMap f x = asum (map f x)

noughtmare / Gram2.hs

Last active July 19, 2024 22:41

Parsing context free grammars based on https://www.well-typed.com/blog/2020/06/fix-ing-regular-expressions/#references

	{-# LANGUAGE GHC2021, GADTs, DataKinds #-}

	import Control.Monad (ap, (>=>))
	import Control.Applicative
	import Prelude hiding (or)
	import Data.Kind
	import Data.Char

	type Ctx :: Type
	type Ctx = [Type]

noughtmare / Gram.hs

Created July 19, 2024 15:44

Recognizing context free grammars based on https://www.well-typed.com/blog/2020/06/fix-ing-regular-expressions/#references

	{- cabal:
	build-depends: base, liquidhaskell == 0.9.6.*
	-}
	{- project:
	allow-newer: bytestring
	-}
	{-# LANGUAGE GHC2021 #-}
	{-# OPTIONS_GHC -Wall -fplugin=LiquidHaskell #-}

	-- Liquid Haskell checks termination for us, but you can disable it if you want.

noughtmare / 1-Parser.agda

Last active June 30, 2024 13:10

Total parser combinators in guarded cubical agda.

	{-# OPTIONS --guarded --rewriting --cubical -WnoUnsupportedIndexedMatch #-}

	module 1-Parser where

	open import 2-Guarded

	open import Data.Product hiding (_<*>_)
	open import Data.Char hiding (_≤_)
	open import Data.Bool hiding (_≤_)
	open import Function

noughtmare / murmurHash3_x64_128.hs

Last active March 14, 2024 00:19

Murmur3 x64 128 hash

	{-# LANGUAGE MagicHash #-}

	import GHC.Exts
	import Foreign
	import GHC.Word
	import Control.Arrow ((>>>))

	rotl64 :: Word64 -> Int -> Word64
	rotl64 (W64# x#) (I# i#) = W64# ((x# `uncheckedShiftL64#` i#) `or64#` (x# `uncheckedShiftRL64#` (64# -# i#)))

noughtmare / 1brc.hs

Last active March 14, 2024 11:36

1brc solution based on @Bodigrim's solution, but with linearly probed primitive hash table

	#!/usr/bin/env cabal
	{- cabal:
	build-depends: base >= 4.19, bytestring, primitive >= 0.9, mmap
	default-language: GHC2021
	ghc-options: -Wall -O2 -fllvm
	-}
	{-# LANGUAGE ExtendedLiterals #-}
	{-# LANGUAGE MagicHash, UnboxedTuples, UnliftedDatatypes #-}

	import Data.ByteString (ByteString)

noughtmare / AbstractMachine.hs

Created December 18, 2023 21:26

Sestoft Lazy Abstract Machine

	import qualified Data.Map.Strict as Map

	data Exp = Var String \| Lam String Exp \| App Exp String \| Let String Exp Exp
	\| Con String [String] \| Case Exp (Map.Map String ([String], Exp))
	deriving Show

	data State = State Heap Control Environment Stack deriving Show

	data Heap = Heap !Int !(Map.Map String (Exp, Environment)) deriving Show
	type Control = Exp

Jaro noughtmare