haskell

References

Summary

Functional language

Haskell doesn't have variables in the sense of an imperative language All "variables" are really explicit values that we give a name

This is actually fantastic for optimization

Commands

The Prelude

The functions that haskell natively has, before you import anything

Reshapers

  1. foldr

    foldr :: (a -> b -> b) -> b -> [a] -> b

    (a -> b -> b) is the kind of shape that a node (:) has. So we can write

    foldr (:) z [1,2,3]
    

    to replace

  2. map

    Applies a function elementwise to a list

    map :: (a -> b) -> [a] -> [b]
  3. concatMap

    Applies a function f to each element in a list, giving you a list of lists. Then it concatenates the nested list into a single list

    map :: (a -> [b]) -> [a] -> [b]
  4. filter

    Evaluates a predicate function against each item in a list. If the predicate returns true, the item stays, if false, it's dropped

    (a -> Bool) -> [a] -> [a]

Folds

Basically these things take a list and replace all of the cons operators (:) with a specified function f, and replace the empty list [ ], with a base-case z

  1. foldr

    Processes a list from right to left

    (a -> b -> b) -> b -> [a] -> b

    The first object is f

    The second is z The third is your list

    Basically f z [1,2,3] becomes f1(f2(f3(z)))

    So basically, it allows you to evaluate a composition of functions fi :: b → b on a fixed element z

    Note: foldr is computed lazily

  2. foldl / foldl'

    Processes a list from left to right

    (b -> a -> b) -> b -> [a] -> b

    The first object is g

    The second element is the base case The third is the list

    We get g(g(g(z,1),2),3) = g3(g2(g1(z)))

    Note: Haskell's laziness treats this a little weird

    Note: foldl' is usually better, because it evaluates at each step, instead of combining a bunch of unexecuted lazy expressions

Linkers and Slicers

  1. zip

    Takes two lists and locks them together into a list of tuples

    [a] -> [b] -> [(a,b)]
  2. zipWith

    Takes two lists, matches them index-by-index and applies a combining function

    zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
  3. replicate

    Creates a list where every element has the same value

    replicate :: Int -> a -> [a]
  4. take / drop

    take n grabs the first n elements of a list and drops the rest drop n drops the first n elements from the list and returns the rest

    Int -> [a] -> [a]

Combinations

  1. Function composition

    (b -> c) -> (a -> b) -> a -> c
  2. Evaluation on a value

    (a - > b) -> a -> b

Compiler

Haskell's compiler is the Glasgow Haskell Compiler (GHC)

We can alter its behaviour using a language pragma: {-# LANGUAGE [option] #-}

{-# LANGUAGE OverloadedStrings #-}

This tells GHC to treat strings as arrays of bytes, as opposed to inefficient linked lists of characters.

Types

Word64

Unsigned 64-bit integer

data

Sum Types

data sumTypeName
  = constructor1 Type1
  | constructor2 Type2
  deriving (Show, Eq)

Constructors are functions that instantiate values. The Type next to them is what you have to pass into the function

What's happening under the hood, is that we get a function

constructor1 :: Type1 -> sumTypeName

Sum types say that the data type can be instantiated by any of the listed constructors.

deriving(Show, Eq): these are properties we give our defined type

Product Types

data prodTypeName = prodTypeName
  { regionName        :: Text
  , regulatoryBody    :: Maybe Text
  , sovereignRiskTier :: Int
  } deriving (Show, Eq)

This says that the data constructor is also prodTypeName

The info inside of the curly brackets are records: they tell us what information our data type must contain (it has to contain all of them)

field :: Type means that the field has the type Type

Maybe is a nice way of preventing null-pointer errors. Maybe Type means that either the field can be type Type or type Nothing

Synonyms

type aliasName = Text

This creates an alias for the type Text

newtype

newtype doesn't have any runtime cost, unlike data

newtype SemanticID = SemanticID Word64

In this snippet, two things are happening:

  1. We're defining a new type called SemanticID
  2. We're also defining a data constructor named SemanticID

The point is that now that SemanticID is created from a 64-bit integer, but it isn't itself considered a 64-bit integer by the program

Characters

All characters are boxed

They're made up of

Lists

Lists are denoted with square brackets, like [1,2,3], but their actual structure under-the-hood is nested constructors:

1 : (2 : (3 : []))

The colon : is called a node or a cons operator. It's actually a function with shape

(:) :: a -> [a] -> [a]

It takes an element of type a and a list of type [a] and returns a list of type [a] :: defines a type

A node contains two pointers:

  1. to the associated character
  2. to the next node (or to [ ])
myList = 1 : 2 : 3 : []

-- is the same as
1 : (2 : (3 : []))
-- because : is defined to work from right to left


(:) :: a -> [a] -> [a]

Disadvantages

Lists are stored non-contiguously

Because lists are generated lazily, if you need to go through an entire list, it's inefficient

A single character usually takes 1-2 bytes in another language. In a haskell list, on average, a character takes up to 24 bytes because it's really made up of

Advantages

Lists are generated lazily

You can prepend data in O(1)

Strings

In basic haskell, String is an alias for a list of characters:

type String = [Char]

Consequently, it's a long chain of nodes:

h : e : l : l : o : []

Since each character is blocked, they're all scattered around the heap, which makes them slow to read

Concatenation

<> is actually the operator for the semigroup typeclass

Modules

module Name where

import Namespace1 (Type1)
import Namespace2 (Type2)

module...where says that anything within the file belongs to the module Name.

import Namespace (Type) grabs certain types from external libraries

Data.Bits

Gives you highly optimized bit-fiddling operations that compile down to assembly instructions, like popcnt and pxor

Data.Text

Treats strings as contiguous byte arrays encoded in UTF-16

Because it's contiguous, you don't need pointers, since you know that the next character is just in the next part of the cache line

splitOn

Text → Text  → [Text]

Scans the text block for every occurance of a fixed string and breaks it into a list at those points.

strip

Text → Text

Trims all leading and trailing whitespace

null

Text → Bool

Checks if your text is empty

toLower

Text → Text

Makes all of the letters lowercase

words

Text  → [Text]

Splits text into a list of words

It's actually smarter than splitOn, which doesn't know how to handle double-spaces or other kinds of white spaces, like tabs, newlines, and carriage returns.

filter

(Char → Bool) → Text → Text

Retains only the characters that match a given filter

Note that unlike words, this returns plain text, not a list.

length

Returns the total number of characters

intercalate

Takes in a seperator list and a list of lists

intercalate :: [a] -> [[a]] -> [a]

qualified

import qualified Data.Text as T

qualified ... as says that every function imported from Data.Text will be prefixed by "T."

Functions

computeSimHash :: [Text] -> SemanticID
computeSimHash tokens = SemanticID $ foldr buildBits 0 (zip [0..63] vectorSums)
  where
    tokenHashes = map hash64 tokens
    vectorSums  = foldr accumulate (replicate 64 0) tokenHashes

foldr takes a higher order function, an initial accumulator state, and a list, and collapses the list down to a single value from right to left

where gives the variables local scope let ... in also gives local scope

zip [0..63]

zipWith takes a function that accepts 2 arguments, and zips two lists together by applying the function to their elements.

\ is the syntax for an anonymous (lambda) function

. is the function composition operator (it goes from right to left, so it behaves like g ˆ f)

$ applies a function to a value to produce a value

<$> takes a function and reaches inside of a container to apply the function inside the container

tokenHashes :: [Word64]
tokenHashes = map hash64 tokens

-- it's the same as
-- const tokenHashes = map(hash64, tokens);

This snippet defines tokenHashes as a list (square brackets) of integers

The next line then describes how we get this list of integers

Case

case sentences of
    []         -> ""
    [single]   -> single
    (first:xs) -> first <> " . " <> last xs

<> monoidal concatenation

Pointfree Style

-- Pointful (Explicit values/elements)
process txt = show $ hash64 $ txt

-- Pointfree (Pure Category-theoretic Arrow Composition)
process = show . hash64

Fat Arrow

=> denotes a type-class constraint

Monads

Ordinarily, the compiler is able to execute things in whatever order will be most optimal

Monads force things to evaluate in sequence

When would you use this?

When interacting with hardware states

Monad Types

PrimMonad

Can execute raw, low-level things

  1. IO Monad

    Can mutate memory, talk to the disk, print to the screen, write to a file

  2. ST Monad

    Memory sandbox that allows mutation, but can't interact with the outside world

    Designed for single-thread deterministic execution

PrimState

  1. RealWorld

    The IO monad has this state

  2. s (sandbox)

    The ST monad has this state

Optimizing

Streaming-Mutation

When you mutate a string, you never want to store the whole string and then mutate it, because you'll get a string scattered throughout the heap

Instead, you modify in place, one letter at a time

Scoping

let … in

let can be used anywhere in your code that a value is expected

in defines the expression where the local variables are valid

calculateArea :: Double -> Double
calculateArea radius = 
    let piVal = 3.14159
        r2    = radius * radius
    in piVal * r2

let ... in is used typically inside of lambda functions or if-thens, where where can't be used

where

It's very similar to let, but you have to use it inside of a function

calculateArea :: Double -> Double
calculateArea radius = piVal * r2
  where piVal = 3.14159
        r2    = radius * radius

It can also work across sum-types:

describeNumber :: Int -> String
describeNumber n
    | n > 0     = "Positive: " ++ show n
    | n < 0     = "Negative: " ++ show n
    | otherwise = "Zero"
    where nSquared = n * n -- This nSquared is available to ALL guards (|)

Pattern Matching

case … of

case takes a value and compares it against a series of patterns, to decide what to return

case expression of
    pattern1 -> result1
    pattern2 -> result2
    _        -> defaultResult

functions in haskell are computed using case...of, under the hood

factorial :: Int -> Int
factorial x = case x of
    0 -> 1
    n -> n * factorial (n - 1)

case ... of and if ... then are computed in the exact same way

but case is often clearer, and allows you to handle more cases, without having to nest a bunch of if statements.