Decomposing a string into its elements

import Data.Char (isLetter, toLower)
import Data.Function.Memoize (memoFix)
import Data.List (intercalate, isPrefixOf)
import System.Environment (getArgs)

elements = [ "H"  , "He" , "Li" , "Be" , "B"  , "C"  , "N"  , "O"  , "F"
           , "Ne" , "Na" , "Mg" , "Al" , "Si" , "P"  , "S"  , "Cl" , "Ar"
           , "K"  , "Ca" , "Sc" , "Ti" , "V"  , "Cr" , "Mn" , "Fe" , "Co"
           , "Ni" , "Cu" , "Zn" , "Ga" , "Ge" , "As" , "Se" , "Br" , "Kr"
           , "Rb" , "Sr" , "Y"  , "Zr" , "Nb" , "Mo" , "Tc" , "Ru" , "Rh"
           , "Pd" , "Ag" , "Cd" , "In" , "Sn" , "Sb" , "Te" , "I"  , "Xe"
           , "Cs" , "Ba" , "La" , "Ce" , "Pr" , "Nd" , "Pm" , "Sm" , "Eu"
           , "Gd" , "Tb" , "Dy" , "Ho" , "Er" , "Tm" , "Yb" , "Lu" , "Hf"
           , "Ta" , "W"  , "Re" , "Os" , "Ir" , "Pt" , "Au" , "Hg" , "Tl"
           , "Pb" , "Bi" , "Po" , "At" , "Rn" , "Fr" , "Ra" , "Ac" , "Th"
           , "Pa" , "U"  , "Np" , "Pu" , "Am" , "Cm" , "Bk" , "Cf" , "Es"
           , "Fm" , "Md" , "No" , "Lr" , "Rf" , "Db" , "Sg" , "Bh" , "Hs"
           , "Mt" , "Ds" , "Rg" , "Cn" , "Uut", "Uuq", "Uup", "Uuh", "Uus"
           , "Uuo" ]

elementize = memoFix (\fn str ->
  if null str
    then return []
    else do element <- filterPrefixes elements str
            soln <- fn $ drop (length element) str
            return $ element : soln)
  where toLowerStr = map toLower
        filterPrefixes prefixes str = filter
          (\x -> isPrefixOf (toLowerStr x) (toLowerStr str))
          prefixes

main = do args <- getArgs
          putStrLn $ intercalate"\n"  $ map (intercalate " ")
            (elementize $ filter isLetter $ concat args)

$ ./elementizer hi esther
H I Es Th Er

1. No N Re P Re Se N Ta Ti O Na Li Sm
2. N O N Re P Re Se N Ta Ti O Na Li Sm
3. No N Re P Re Se N Ta Ti O N Al I Sm
4. N O N Re P Re Se N Ta Ti O N Al I Sm

The Di Vergent Code

Prologue

Chapter 1

CARNEGIE MELLON UNIVERSITY
proudly presents
an evening with Robert Langdon
Professor of Symbolic Systems, Stanford University

Chapter 2

Welcome to the Lambda Oracle, version 1.0.0.
Copyright © 1936. The Church of Alonzo.
Enter terms at the prompt.
$

Chapter 3

Welcome to the Lambda Oracle, version 1.0.0.
Copyright © 1936. The Church of Alonzo.
Enter terms at the prompt.
$ λx. x
Result: λx. x

$ (λx. x) λx. x
Result: λx. x

$ λf. λx. f x
Result: λf. λx. f x

Chapter 4

$ (λx. x x) λx. x x
(λx. x x) λx. x x
(λx. x x) λx. x x
(λx. x x) λx. x x
(λx. x x) λx. x x
...

Chapter 5

Chapter 6

(λx. x x) λx. x x

λf. (λx. f (x x)) (λx. f (x x))

(λf. (λx. f (x x)) (λx. f (x x))) g
= (λx. g (x x)) (λx. g (x x))
= g ((λx. g (x x)) (λx. g (x x)))

Y λf. λn. 1 if n == 0 else n * f (n - 1) end

Chapter 7

Formalizing dynamic scoping

Lexical vs. dynamic scoping

(function(x) {
  return (function(x) {
    return function() {
      return x;
    };
  })('lexical')();
})('dynamic')

((lambda (x)
  (funcall ((lambda (x)
    (lambda ()
      x
    )
  ) "lexical"))
) "dynamic")

The lambda calculus

Syntax

• Variable: \( x \)
• Abstraction: \( \lambda x . t \) (where \( t \) extends as far right as possible)
• Application: \( t_1 \: t_2 \) (left-associative)

Semantics

Example

Semantics for dynamic scoping

Example

Conclusion

Higher-rank and higher-kinded types

Background: what is parametric polymorphism?

String chooseString(String head, String tail) {
  if (Math.random() < 0.5) {
    return head;
  } else {
    return tail;
  }
}

<T> T chooseValue(T head, T tail) {
  if (Math.random() < 0.5) {
    return head;
  } else {
    return tail;
  }
}

Higher-rank types

String chooseStringWeird(
  <T> BiFunction<T, T, T> randomChoice,
  String head,
  String tail
) {
  if (randomChoice(true, false)) {
    return randomChoice(head, tail);
  } else {
    return randomChoice(tail, head);
  }
}

String bestEditor() {
  return chooseStringWeird(chooseValue, "emacs", "vim");
}

Higher-kinded types

Stack<String> names;

class GraphSearch<T> {
  T<Node> frontier;
}

GraphSearch<Stack> depthFirstSearch;
GraphSearch<Queue> breadthFirstSearch;

Conclusion

Footnotes

Does Google execute JavaScript?

1. The HTML from the server contains text which says “Google does not execute JavaScript.”
2. There is some inline JavaScript on the page that changes the text to “Google executes JavaScript, but only if it is embedded in the document.”
3. The HTML also links to a script which, when loaded, changes the text to “Google executes JavaScript, even if the script is fetched from the network. However, Google does not make AJAX requests.”
4. That script makes an AJAX request and updates the text with the response from the server. The server returns the message “Google executes JavaScript and even makes AJAX requests.”