In this article, I'll explain why implementing numbers with just algebraic datatypes is desirable. I'll then talk about common implementations of FFT (Fast Fourier Transform) and why they hide inherent inefficiencies. I'll then show how to implement integers and complex numbers with just algebraic datatypes, in a way that is extremely simple and elegant. I'll conclude by deriving a pure functional implementation of complex FFT with just datatypes, no floats.
Disclaimer: This piece is written anonymously. The names of a few particular companies are mentioned, but as common examples only.
This is a short write-up on things that I wish I'd known and considered before joining a private company (aka startup, aka unicorn in some cases). I'm not trying to make the case that you should never join a private company, but the power imbalance between founder and employee is extreme, and that potential candidates would
A primer/refresher on the category theory concepts that most commonly crop up in conversations about Scala or FP. (Because it's embarassing when I forget this stuff!)
I'll be assuming Scalaz imports in code samples, and some of the code may be pseudo-Scala.
A functor is something that supports map
.
{ | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"# The unreasonable effectiveness of Character-level Language Models\n", | |
"## (and why RNNs are still cool)\n", | |
"\n", | |
"###[Yoav Goldberg](http://www.cs.biu.ac.il/~yogo)\n", |
import code; code.interact(local=dict(globals(), **locals())) |
### | |
# Scheme code is translated to YARV byte code, then evaluated in the | |
# Ruby Virtual Machine | |
require 'rbconfig' | |
require 'dl' | |
require 'fiddle' | |
require 'strscan' | |
class RubyVM |
# The common one, converted to CoffeeScript | |
y = (f) -> ((y)-> y y) (y) -> f (n) -> (y y) n | |
# My version | |
y = ((y)->y y) (y) -> (f) -> (n) -> (f (y y) f) n | |
fact = y (f) -> (n) -> if n is 0 then 1 else n * f n-1 | |
# And a simpler way, requires a different `fact` that passes itself to itself | |
y = (f) -> (n) -> (f f) n |