Joey Eremondi JoeyEremondi

A common misconception about functional languages is that they are slow, and that function calls is inherently slow compared to looping. However, most functional languages, and now Elm, provide a way for you to write loops: tail-recursion.

What is a Tail Call?

When you define a function, you will usually call other functions to build a return value. But sometimes, you directly return the value returned by another function. This is called a tail call.

Specifically, a an expression is in tail position if it is the body of the function, or if it is in tail position of the result of an if or case statement that is in tail position. Function calls made to calculate argument parameters, or used in the right-hand side of a let declaration, are not in tail position.

Elm TCO

The Transformation

For an example, let's look at the oneOf function from the Maybe module:

oneOf : List (Maybe a) -> Maybe a
oneOf maybes =
  case maybes of

	(custom-set-faces
	;; custom-set-faces was added by Custom.
	;; If you edit it by hand, you could mess it up, so be careful.
	;; Your init file should contain only one such instance.
	;; If there is more than one, they won't work right.
	'(default ((t (:family "Source Code Pro" :foundry "adobe" :slant normal :weight semi-bold :height 113 :width normal)))))

	;;Flycheck hook for haskell-mode
	;;(eval-after-load 'flycheck
	;; '(add-hook 'flycheck-mode-hook #'flycheck-haskell-setup))

	import qualified AST.Module as Module

	----------------------------------------------------------
	-- These are the optimizing functions I'm writing that will be public
	-- JS could be added to the output Map as well, if we wanted

	{-\| Given interfaces from compiled Elm modules and their compiled JavaScript,
	attempt to optimize the given modules, assuming that the program will be run from
	the entry point of `main` within the given main module-}
	optimizeProgram

	import Text (asText)

	type alias Foo a b = {a \| x:Int, y:b}

	type alias Bar a b = {a \| y:b, z:Int}

	type alias FooBar a b = Foo (Bar a b) b


	myRec : Foo (Bar {} Int) Int

	As a learning experience, I'm trying to implement a verified regular-expression matcher using continuation-passing style in Agda, based on the one proposed in [this paper](http://www.cs.cmu.edu/~rwh/papers/regexp/jfp.pdf).

	I've got a type for regular expressions defined like this:

	<!-- language: lang-agda -->

	data RE : Set where
	ε : RE
	∅ : RE
	Lit : Char -> RE

	I'm going to talk about Monads as they are used in programming, without reference to the category theory (in no small part because I don't understand it entirely myself).

	Monads are present in many languages, with various names. Elm has them as [Tasks](http://elm-lang.org/blog/announce/0.15.elm), and F# has them as [Computation Expressions](https://msdn.microsoft.com/en-us/library/dd233182.aspx). You could write something equivalent in JavaScript, Python, or any language supporting higher-order functions.

	To understand what they are, you need to understand what a type constructor is. A type constructor is something which, when given a specific type as an argument, forms a type.

	In Haskell notation, `List` is a type constructor. It's not a full type, because you don't know what it is a list of. `List Int` is a type, as is `List Bool`, or `List (List Double)`. This is similar to generics in Java or Templates in C++: you can't have just a List, you need `List<int>` or something like that.

	Now, "monad" is an

	import Dict
	import Random

	import Graphics.Element

	-- port initialSeed : Int

	maxSize = 1000000
	numToInsert = 10000

	module Benchmark
	( Benchmark
	, Suite
	, run
	, bench1
	, bench2
	, bench3
	, bench4
	, bench5
	, bench6

	var Elm = Elm \|\| { Native: {} };
	Elm.Array = Elm.Array \|\| {};
	Elm.Array.make = function (_elm) {
	"use strict";
	_elm.Array = _elm.Array \|\| {};
	if (_elm.Array.values)
	return _elm.Array.values;
	var _op = {},
	_N = Elm.Native,
	_U = _N.Utils.make(_elm),