monadplus

{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE UndecidableInstances #-}

-- Source: https://wiki.haskell.org/ListT_done_right

-- The reason why https://hackage.haskell.org/package/mtl-2.2.2/docs/Control-Monad-List.html is broken:
--    * ListT imposes unnecessary strictness.
--    * ListT isn't really a monad transformer, ie. ListT m isn't always a monad for a monad m.

monadplus

data Tree' a = Leaf' | Node' a (Tree a) (Tree a)
data Tree a = Tree { root :: Tree' a, force :: () }

instance NFData a => NFData (Tree a) where
  rnf = force

node :: NFData a => a -> Tree a -> Tree a -> Tree a
node x l r = Tree (Node' x l r) (rnf x `seq` rnf l `seq` rnf r)

monadplus

Source: https://doisinkidney.com/posts/2020-05-02-more-random-access-lists.html

>>> :set -XPolyKinds
>>> :set -XKindSignatures    
>>> :set -XTypeFamilies 
>>> :set -XTypeFamilyDependencies 
>>> import Data.Kind

>>> type family The k = (s :: k -> Type) | s -> k

monadplus

{-# LANGUAGE NumericUnderscores #-}
{-# LANGUAGE ScopedTypeVariables #-}
module Main where

import Test.QuickCheck
import System.IO
import Data.List.Split
import Text.Printf

data DNA

monadplus

The Expression Problem basically states that programs are made up of data types and functions that act on those data types. As a program grows, the number of functions that rely on the structure of those data types also grows. Because of this, extending the program or adding more functionality becomes exponentially more difficult.

monadplus

A*

Compute the shortest path between two vertices of a graph.

• At each step picks the node according to the lowest f(x) = g(x) + h(x)
• g(x) = the movement cost to move from the starting point to a given square
• h(x) = estimated movement cost from that given square to the final destination. Heuristic

Time Complexity

monadplus

Binomial Heaps [Vui78, Bro78]

Common implementation of heaps. [Easy to implement as a purely functional data structure][1].

Complexity

Operation	Binary	Binomial	Fibonacci
Find-min	Θ(1)	Θ(1)	Θ(1)
delete-min	Θ(log n)	Θ(log n)	O(log n)

monadplus

# Requires LLVM 6.0 installed
ghc -fllvm -optlo-O3 bubblesort.hs

monadplus

{-# LANGUAGE TemplateHaskell #-}
module TH (
  deriveSetters
) where

import           Control.Monad       (forM)
import           Data.List           (nub)
import           Language.Haskell.TH

-- From field name to update function

monadplus

-- Common Table Expressions

-- : Problem

-- 1) For each film count the number of actors starring in it
SELECT f.id, count(*) as actors FROM films f LEFT JOIN films_actors fa ON f.id = fa.film_id GROUP BY f.id;

-- 2) For each film, #actors, its prequel and sequel count number of actors starring in them.
SELECT films.id, films.prequel_id, films.sequel_id,
films.actors AS actors,