hamt/HAMTPresentation.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "{-# LANGUAGE GeneralizedNewtypeDeriving #-}\n",
    "{-# LANGUAGE TypeSynonymInstances #-}\n",
    "{-# LANGUAGE FlexibleInstances #-}\n",
    "\n",
    "import Data.Bits             (Bits (bit, complement, popCount, shiftR, (.&.), (.|.)),\n",
    "                              FiniteBits (finiteBitSize))\n",
    "import Data.ByteArray.Hash   (FnvHash32 (..), fnv1Hash)\n",
    "import Data.ByteString.Char8 (pack)\n",
    "import Data.Char             (intToDigit)\n",
    "import Data.Semigroup        ((<>))\n",
    "import Data.Vector           (Vector, drop, singleton, take, (!), (//))\n",
    "import Data.Word             (Word16, Word32)\n",
    "import Numeric               (showIntAtBase)\n",
    "import Prelude               hiding (drop, lookup, take)\n",
    "import System.TimeIt         (timeIt)\n",
    "import Text.Show.Pretty      (pPrint)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "newtype Binary a = Binary a deriving (Enum, Ord, Real, Integral, Eq, Num, Bits, FiniteBits)\n",
    "\n",
    "instance (FiniteBits a, Show a, Integral a) => Show (Binary a) where\n",
    "    show (Binary a) = let\n",
    "        str = showIntAtBase 2 intToDigit a \"\"\n",
    "        size = finiteBitSize a\n",
    "        in replicate (size - length str) '0' <> str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "type Hash = Binary Word32\n",
    "\n",
    "class Hashable a where\n",
    "    hash :: a -> Hash"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "instance Hashable String where\n",
    "    hash s = let\n",
    "        FnvHash32 h = fnv1Hash (pack s)\n",
    "        in Binary h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "type Bitmap = Binary Word16\n",
    "\n",
    "bitsPerSubkey :: Int\n",
    "bitsPerSubkey = 4\n",
    "\n",
    "type Shift = Int"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "insertAt :: Vector a -> Int -> a -> Vector a\n",
    "insertAt vector index a = take index vector <> singleton a <> drop index vector\n",
    "\n",
    "updateAt :: Vector a -> Int -> a -> Vector a\n",
    "updateAt vector index a = vector // [(index, a)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data HAMT key value\n",
    "    = None\n",
    "    | Leaf Hash key value\n",
    "    | Many Bitmap (Vector (HAMT key value))\n",
    "    deriving (Show)\n",
    "\n",
    "empty :: HAMT key value\n",
    "empty = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "name": "haskell",
   "pygments_lexer": "Haskell",
   "version": "8.4.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}