Skip to content

Instantly share code, notes, and snippets.

@macobo

macobo/gist:5523724

Last active December 17, 2015 00:49
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save macobo/5523724 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save macobo/5523724 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.txt
{
"metadata": {
"name": "LambdaCalculus"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Lambda calculus pythonis <span style=\"font-weight: normal; float:right;\">Karl-Aksel Puulmann, kevad 2013</span>"
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Sissejuhatus"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def add(a, b):\n",
" return a + b\n",
"\n",
"add = lambda x, y: x + y \n",
"add(5, 6)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 42,
"text": [
"11"
]
}
],
"prompt_number": 42
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def add(a):\n",
" def curried(b):\n",
" # haskell curry!\n",
" return a + b\n",
" return curried\n",
"\n",
"add = lambda x: lambda y: x + y\n",
"add(5)(6)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 46,
"text": [
"11"
]
}
],
"prompt_number": 46
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"add5 = add(5) # karritatud funktsioon\n",
"add5(6)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 180,
"text": [
"11"
]
}
],
"prompt_number": 180
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(lambda x: lambda y: x + y)(5)(6) # anon\u00fc\u00fcmne!"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 181,
"text": [
"11"
]
}
],
"prompt_number": 181
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Kaotame \u00e4ra pythonist k\u00f5ik peale funktsioonide defineerimise ja nende v\u00e4lja kutsumise ja \u00fcritame selle peale \u00fcles ehitada keelt, mis oleks sama v\u00f5imas kui python ise.\n",
"\n",
"Reeglid:\n",
"\n",
"* Kasutame ainult karritatud funktsioone ja nende v\u00e4lja kutsumist. K\u00f5ik muu pythoni keelest unustame \u00e4ra!\n",
"* Me v\u00f5ime k\u00fcll anda funktsioonidele nimed, aga hiljem peab olema iga nimi asendatav oma v\u00e4\u00e4rtusega."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# abi\u00fclesanne, mida \u00fcritame oma uues keeles v\u00e4ljendada\n",
"# kuidas v\u00e4him v\u00f5imalik arv m\u00fcnte kulutada arve (t\u00e4pseks) maksmiseks?\n",
"\n",
"def min_length(a, b):\n",
" if not b or (len(a) < len(b) and a):\n",
" return a\n",
" else:\n",
" return b\n",
"\n",
"def coin_change(amount, coins, taken = []):\n",
" if amount == sum(taken):\n",
" return taken\n",
" if coins == []:\n",
" return []\n",
" return min_length(coin_change(amount, coins[1:], [coins[0]]+taken),\n",
" coin_change(amount, coins[1:], taken))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 186
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"coin_change(15, [1,2,3,4,5,6,7,8])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 187,
"text": [
"[8, 7]"
]
}
],
"prompt_number": 187
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"coin_change(13, [4,4,4,3])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 188,
"text": [
"[]"
]
}
],
"prompt_number": 188
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Numbrid"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# church numerals\n",
"ZERO = lambda f: lambda x: x\n",
"ONE = lambda f: lambda x: f(x)\n",
"TWO = lambda f: lambda x: f(f(x))\n",
"THREE = lambda f: lambda x: f(f(f(x)))\n",
"FOUR = lambda f: lambda x: f(f(f(f(x))))\n",
"FIVE = lambda f: lambda x: f(f(f(f(f(x)))))\n",
"TEN = lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x))))))))))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 5
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"FIVE"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 165,
"text": [
"<function __main__.<lambda>>"
]
}
],
"prompt_number": 165
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def to_int(num):\n",
" \" Convering the numerals to a form we can read \"\n",
" return num(lambda x: x+1)(0)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 7
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"to_int(ZERO)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 166,
"text": [
"0"
]
}
],
"prompt_number": 166
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"to_int(FIVE)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 9,
"text": [
"5"
]
}
],
"prompt_number": 9
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# http://en.wikipedia.org/wiki/Lambda_calculus#Arithmetic_in_lambda_calculus\n",
"INCREMENT = lambda num: lambda f: lambda x: f(num(f)(x))\n",
"DECREMENT = lambda num: lambda f: lambda x: \\\n",
" num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)\n",
"\n",
"SIX = INCREMENT(FIVE)\n",
"\n",
"assert to_int(SIX) == 6\n",
"assert to_int(DECREMENT(ONE)) == 0\n",
"assert to_int(DECREMENT(FIVE)) == 4"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 10
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"PLUS = lambda a: lambda b: a(INCREMENT)(b)\n",
"MINUS = lambda a: lambda b: b(DECREMENT)(a)\n",
"MULTIPLY = lambda a: lambda b: a(PLUS(b))(ZERO) # a+a+a+...+a b times\n",
"POWER = lambda a: lambda b: b(a)\n",
" \n",
"NINE = MULTIPLY(THREE)(THREE)\n",
"FIFTEEN = MULTIPLY(FIVE)(THREE)\n",
"THIRTY = MULTIPLY(SIX)(FIVE)\n",
"\n",
"assert to_int(PLUS(THREE)(FIVE)) == 8\n",
"assert to_int(MINUS(FIVE)(THREE)) == 2\n",
"assert to_int(MINUS(THREE)(FIVE)) == 0 # !!!\n",
"assert to_int(THIRTY) == 30\n",
"assert to_int(POWER(THREE)(FIVE)) == 243"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 11
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**NB:** Kuna me lubasime, et k\u00f5ik meie poolt defineeritud nimed peab olema v\u00f5imalik tema v\u00e4\u00e4rtusega asendada, siis on j\u00e4rgnevad samav\u00e4\u00e4rsed:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"PLUS\n",
"lambda a: lambda b: a(INCREMENT)(b)\n",
"lambda a: lambda b: a(lambda num: lambda f: lambda x: f(num(f)(x)))(b)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 177,
"text": [
"<function __main__.<lambda>>"
]
}
],
"prompt_number": 177
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Sama ka n\u00e4iteks liitmisel"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"to_int(PLUS(THREE)(TWO))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 178,
"text": [
"5"
]
}
],
"prompt_number": 178
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"to_int((lambda a: lambda b: a((lambda num: lambda f: lambda x: f(num(f)(x))))(b))((lambda f: lambda x: f(f(f(x)))))((lambda f: lambda x: f(f(x)))))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 179,
"text": [
"5"
]
}
],
"prompt_number": 179
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Loogika"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"TRUE = lambda a: lambda b: a\n",
"FALSE = lambda a: lambda b: b\n",
" \n",
"def to_bool(f):\n",
" return f(True)(False)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 12
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"to_bool(TRUE)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 13,
"text": [
"True"
]
}
],
"prompt_number": 13
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"IF = lambda boolean: lambda left: lambda right: boolean(left)(right)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 14
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"IF(TRUE)(\"Cake\")(\"Death\")"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 167,
"text": [
"'Cake'"
]
}
],
"prompt_number": 167
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Vaatame, kas saame IF-i lihtsamaks teha. Vaatleme analoogset funktsiooni:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# n\u00e4iteks\n",
"f1 = lambda x: lambda y: x(y)\n",
"f2 = (lambda x: x)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 185
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Kui vaadata, mida f1 teeb, siis ta esimese argumendi andmisel funktsiooni, mis v\u00f5tab teise argumendi ja rakendab esimest argumendiga teine. \n",
"\n",
"Kui aga x on funktsioon, on see t\u00e4pselt sama, mida teeb f2 talle teise argumendi andmisel - need kaks definitsiooni om samav\u00e4\u00e4rsed!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Kui n\u00fc\u00fcd vaadata meie IF-i, siis siin on sama muster lausa kaks korda. Seega saab lihtsustada:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# simplify it further!\n",
"IF = lambda boolean: boolean"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 16
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"AND = lambda a: lambda b: IF(a)(b)(FALSE)\n",
"OR = lambda a: lambda b: IF(a)(TRUE)(b)\n",
"NOT = lambda a: IF(a)(FALSE)(TRUE)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 17
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"assert AND(TRUE)(FALSE) == FALSE\n",
"assert AND(TRUE)(TRUE) == TRUE\n",
"assert OR(TRUE)(FALSE) == TRUE\n",
"assert NOT(TRUE) == FALSE"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 18
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"IS_ZERO = lambda num: num(lambda x: FALSE)(TRUE) # only ZERO will call the second argument\n",
"\n",
"LESS_THAN_EQUAL = lambda a: lambda b: IS_ZERO(MINUS(a)(b)) # 3-5 is 0 with our numbers\n",
"\n",
"EQUAL = lambda a: lambda b: AND(LESS_THAN_EQUAL(a)(b))(LESS_THAN_EQUAL(b)(a))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 19
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"assert IS_ZERO(ZERO) == TRUE\n",
"assert IS_ZERO(FIVE) == FALSE\n",
"assert LESS_THAN_EQUAL(THREE)(FIVE) == TRUE\n",
"assert LESS_THAN_EQUAL(FIVE)(THREE) == FALSE"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 20
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"IF(LESS_THAN_EQUAL(THREE)(FIVE))(\"3 <= 5\")(\"3 > 5\")"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 91,
"text": [
"'3 <= 5'"
]
}
],
"prompt_number": 91
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Listid"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ehitame \u00fcles linked-listid."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"PAIR = lambda head: lambda tail: lambda f: f(head)(tail)\n",
"LEFT = lambda pair: pair(TRUE) # TRUE = lambda x: lambda y: x\n",
"RIGHT = lambda pair: pair(FALSE)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 22
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"NIL = PAIR(TRUE)(TRUE)\n",
"HEAD = lambda lst: LEFT(RIGHT(lst))\n",
"TAIL = lambda lst: RIGHT(RIGHT(lst))\n",
"\n",
"PREPEND = lambda el: lambda lst: PAIR(FALSE)(PAIR(el)(lst))\n",
"IS_EMPTY = LEFT # lambda lst: LEFT(lst)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 23
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"lst = PREPEND(THREE)(PREPEND(ONE)(NIL)) # [3, 1]\n",
"assert to_int(HEAD(lst)) == 3\n",
"assert to_int(HEAD(TAIL(lst))) == 1\n",
"assert IS_EMPTY(NIL) == TRUE\n",
"assert IS_EMPTY(lst) == FALSE\n",
"assert IS_EMPTY(TAIL(TAIL(lst))) == TRUE"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 24
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def to_list(f):\n",
" \" Converts the lambda-calculus list to a normal one \"\n",
" result = []\n",
" while not to_bool(IS_EMPTY(f)):\n",
" result.append(HEAD(f))\n",
" f = TAIL(f)\n",
" return result"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 25
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Eelnevaga v\u00f5ime alguses antud algoritmi muutma hakata."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def min_length(a, b):\n",
" return a if (len(a) < len(b) and a) or (not b) else b\n",
"\n",
"def coin_change(amount, coins, taken = []):\n",
" if amount == sum(taken):\n",
" return taken\n",
" if coins == []:\n",
" return []\n",
" return min_length(coin_change(amount, coins[1:], [coins[0]]+taken),\n",
" coin_change(amount, coins[1:], taken))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 26
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"MIN_LENGTH = lambda a: lambda b: \\\n",
" IF(OR\n",
" (IS_EMPTY(b))\n",
" (AND\n",
" (NOT(IS_EMPTY(a)))\n",
" (len(a) < len(b)))\n",
" )(a)(b)\n",
"\n",
"COIN_CHANGE = lambda amount: lambda coins: lambda taken: \\\n",
" IF(EQUAL(amount)(sum(taken)))(\n",
" taken\n",
" )(IF(IS_EMPTY(coins))\n",
" (NIL)\n",
" (MIN_LENGTH(\n",
" COIN_CHANGE(amount)(TAIL(coins))(PREPEND(HEAD(coins))(taken)))(\n",
" COIN_CHANGE(amount)(TAIL(coins))(taken))))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 27
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Rekursioon"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# the useful list functions - map, filter and reduce\n",
"def map(f, lst): \n",
" return [f(x) for x in lst]\n",
"def filter(predicate, lst):\n",
" return [x for x in lst if predicate(x)]\n",
"def reduce(f, initial, lst):\n",
" if lst == []:\n",
" return initial\n",
" return f(lst[0], reduce(f, initial, lst[1:]))\n",
"\n",
"length = lambda lst: reduce(lambda el, rest: rest + 1, 0, lst)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 189
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"length([1,2,3,4])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 29,
"text": [
"4"
]
}
],
"prompt_number": 29
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"REDUCE = lambda f: lambda init: lambda lst: \\\n",
" IF(IS_EMPTY(lst))(\n",
" init)(\n",
" f(HEAD(lst))(REDUCE(f)(init)(TAIL(lst))))\n",
"#LENGTH = lambda lst: REDUCE(PLUS(ONE))(ZERO)(lst) \n",
"LENGTH = REDUCE(lambda _: PLUS(ONE))(ZERO)\n",
"\n",
"# LENGTH(NIL)chrome\n",
"# RuntimeError: maximum recursion depth exceeded??"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 30
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Rekursioon ei peatunud. \n",
"Probleem selles, et rekursiivne v\u00e4ljakutse REDUCE pihta tehakse agaralt - kohe kui pythoni kood n\u00e4eb seda v\u00e4ljakutset mingi avaldise sees, asub ta kohe v\u00e4ljakutse v\u00e4\u00e4rtust leidma. See t\u00e4hendab, et ka t\u00fchja listi puhul kutsub enne init tagastamist reduce v\u00e4lja <span style=\"color: black; border: 1px solid #DDD; border-radius: 3px; background: #F7F7F7;\">f(HEAD(lst))(REDUCE(f)(init)(TAIL(lst))))</span>\n",
"\n",
"Lahenduseks kasutame sama v\u00f5tet mis enne IF-i lihtsamaks tehes. Kui \n",
"<span style=\"color: black; border: 1px solid #DDD; border-radius: 3px; background: #F7F7F7;\">lambda x: blah(x)</span> \n",
"on sama kui \n",
"<span style=\"color: black; border: 1px solid #DDD; border-radius: 3px; background: #F7F7F7;\">blah</span>, siis on ka vastupidine t\u00f5ene. Funktsiooni ei kutsuta enne v\u00e4lja kui argumendid antud. Seega paneme rekursiivse v\u00e4ljakutse funktsioonidefinitsiooni sisse!"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"REDUCE = lambda f: lambda init: lambda lst: \\\n",
" IF(IS_EMPTY(lst))(\n",
" init)(\n",
" lambda x: ( f(HEAD(lst))(REDUCE(f)(init)(TAIL(lst))) )(x))\n",
"#LENGTH = lambda lst: REDUCE(PLUS(ONE))(ZERO)(lst) \n",
"LENGTH = REDUCE(lambda _: PLUS(ONE))(ZERO)\n",
"to_int(LENGTH(NIL))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 182,
"text": [
"0"
]
}
],
"prompt_number": 182
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Me aga eksime siin oma reeglite vastu - igale funktsioonile nime andmisel olime lubanud, et selle nime saab alati asendada v\u00e4\u00e4rtusega. Aga kui v\u00f5rduse vasakul ja paremal pool on REDUCE, siis see ei ole v\u00f5imalik.\n",
"\n",
"\u00d5nneks on v\u00f5imalik defineerida anon\u00fc\u00fcmseid (nime mittevajavaid) rekursiivseid funktsioone niinimetatud. Y-kombinaatori abil."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# Y-combinator to the rescue\n",
"# \u03bbf.(\u03bbx.f (\u03bbv.((x x) v))) (\u03bbx.f (\u03bbv.((x x) v)))\n",
"Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(\n",
" lambda x: f(lambda v: x(x)(v)))\n",
"\n",
"REDUCE = Y(lambda rec: lambda f: lambda init: lambda lst: \\\n",
" IF(IS_EMPTY(lst))(\n",
" init)(\n",
" lambda x: f(HEAD(lst))(rec(f)(init)(TAIL(lst)))(x)))\n",
"LENGTH = REDUCE(lambda _: PLUS(ONE))(ZERO)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 31
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"to_int(LENGTH(NIL))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 32,
"text": [
"0"
]
}
],
"prompt_number": 32
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"onetwothree = PREPEND(ONE)(PREPEND(TWO)(PREPEND(THREE)(NIL)))\n",
"to_int(LENGTH(onetwothree))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 33,
"text": [
"3"
]
}
],
"prompt_number": 33
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"SUM = REDUCE(PLUS)(ZERO)\n",
"to_int(SUM(onetwothree))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 34,
"text": [
"6"
]
}
],
"prompt_number": 34
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"\u00dchendame uued t\u00f6\u00f6riistad"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# helpers\n",
"def from_int(x):\n",
" return ZERO if x == 0 else INCREMENT(from_int(x-1))\n",
"\n",
"def from_list(list):\n",
" return NIL if list == [] else PREPEND(list[0])(from_list(list[1:]))\n",
"\n",
"RANGE = Y(lambda rec: lambda start: lambda end: \\\n",
" IF(LESS_THAN_EQUAL(end)(start))(\n",
" NIL)(\n",
" lambda x: ( \n",
" PREPEND(start)(rec(INCREMENT(start))(end)) \n",
" )(x)))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 35
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"map(to_int, to_list(RANGE(ZERO)(FIVE)))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 36,
"text": [
"[0, 1, 2, 3, 4]"
]
}
],
"prompt_number": 36
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"MIN_LENGTH = lambda a: lambda b: \\\n",
" IF(OR\n",
" (IS_EMPTY(b))\n",
" (AND\n",
" (NOT(IS_EMPTY(a)))\n",
" (LESS_THAN_EQUAL(LENGTH(a))(LENGTH(b))))\n",
" )(a)(b)\n",
"\n",
"COIN_CHANGE = Y(lambda rec: lambda amount: lambda coins: lambda taken: \\\n",
" IF(EQUAL(amount)(SUM(taken)))\n",
" (taken)\n",
" (IF(IS_EMPTY(coins))\n",
" (NIL)\n",
" (lambda x: MIN_LENGTH\n",
" (rec(amount)(TAIL(coins))(PREPEND(HEAD(coins))(taken)))\n",
" (rec(amount)(TAIL(coins))(taken)) (x))))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 37
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"assert len(to_list(MIN_LENGTH(NIL)(NIL))) == 0 \n",
"assert len(to_list(MIN_LENGTH(NIL)(RANGE(ONE)(THREE)))) == 2\n",
"assert len(to_list(MIN_LENGTH(RANGE(ONE)(FIVE))(RANGE(ONE)(NINE)))) == 4"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 38
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"result = COIN_CHANGE(TEN) (RANGE(ONE)(SIX)) (NIL)\n",
"map(to_int, to_list(result))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 39,
"text": [
"[5, 4, 1]"
]
}
],
"prompt_number": 39
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Tundub, et t\u00f6\u00f6tab. Aga nagu me alguses lubasime, siis annab k\u00f5ik funktsioonidele antud nimed (COIN_CHANGE, TEN jms) asendada neile antud v\u00e4\u00e4rtusega. Teeme seda!"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# sama mis a = COIN_CHANGE(TEN) (RANGE(ONE)(SIX)) (NIL)\n",
"a = ((lambda f:(lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda amount: lambda coins: lambda taken:((lambda boolean: boolean)((lambda a: lambda b:((lambda a: lambda b:((lambda boolean: boolean)(a)(b)((lambda a: lambda b: b))))((lambda a: lambda b:((lambda num: num(lambda x:((lambda a: lambda b: b)))((lambda a: lambda b: a)))((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))))(a)(b))((lambda a: lambda b:((lambda num: num(lambda x:((lambda a: lambda b: b)))((lambda a: lambda b: a)))((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))))(b)(a))))(amount)((((lambda f:(lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda f: lambda init: lambda lst:((lambda boolean: boolean)(((lambda pair: pair((lambda a: lambda b: a))))(lst))(init)(lambda x: f((lambda lst:((lambda pair: pair((lambda a: lambda b: a)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(lst))(rec(f)(init)((lambda lst:((lambda pair: pair((lambda a: lambda b: b)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(lst)))(x)))))((lambda a: lambda b: a((lambda num: lambda f: lambda x: f(num(f)(x))))(b)))((lambda f: lambda x: x)))(taken)))(taken)((lambda boolean: boolean)(((lambda pair: pair((lambda a: lambda b: a))))(coins))(((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: a))((lambda a: lambda b: a))))(lambda x:((lambda a: lambda b:((lambda boolean: boolean)((lambda a: lambda b:((lambda boolean: boolean)(a)((lambda a: lambda b: a))(b)))(((lambda pair: pair((lambda a: lambda b: a))))(b))((lambda a: lambda b:((lambda boolean: boolean)(a)(b)((lambda a: lambda b: b))))((lambda a:((lambda boolean: boolean)(a)((lambda a: lambda b: b))((lambda a: lambda b: a))))(((lambda pair: pair((lambda a: lambda b: a))))(a)))((lambda a: lambda b:((lambda num: num(lambda x:((lambda a: lambda b: b)))((lambda a: lambda b: a)))((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))))((((lambda f:(lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda f: lambda init: lambda lst:((lambda boolean: boolean)(((lambda pair: pair((lambda a: lambda b: a))))(lst))(init)(lambda x: f((lambda lst:((lambda pair: pair((lambda a: lambda b: a)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(lst))(rec(f)(init)((lambda lst:((lambda pair: pair((lambda a: lambda b: b)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(lst)))(x)))))(lambda _:((lambda a: lambda b: a((lambda num: lambda f: lambda x: f(num(f)(x))))(b))((lambda f: lambda x: f(x)))))((lambda f: lambda x: x)))(a))((((lambda f:(lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda f: lambda init: lambda lst:((lambda boolean: boolean)(((lambda pair: pair((lambda a: lambda b: a))))(lst))(init)(lambda x: f((lambda lst:((lambda pair: pair((lambda a: lambda b: a)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(lst))(rec(f)(init)((lambda lst:((lambda pair: pair((lambda a: lambda b: b)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(lst)))(x)))))(lambda _:((lambda a: lambda b: a((lambda num: lambda f: lambda x: f(num(f)(x))))(b))((lambda f: lambda x: f(x)))))((lambda f: lambda x: x)))(b)))))(a)(b)))(rec(amount)((lambda lst:((lambda pair: pair((lambda a: lambda b: b)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(coins))((lambda el: lambda lst:((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((lambda lst:((lambda pair: pair((lambda a: lambda b: a)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(coins))(taken)))(rec(amount)((lambda lst:((lambda pair: pair((lambda a: lambda b: b)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(coins))(taken)))(x))))))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x))))))))))))(((lambda f:(lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda start: lambda end: IF((lambda a: lambda b:((lambda num: num(lambda x:((lambda a: lambda b: b)))((lambda a: lambda b: a)))((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))))(end)(start))(((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: a))((lambda a: lambda b: a))))(lambda x:((lambda el: lambda lst:((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))(start)(rec((lambda num: lambda f: lambda x: f(num(f)(x)))(start))(end)))(x))))((lambda f: lambda x: f(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(x))))))))))(((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: a))((lambda a: lambda b: a))))\n",
"map(to_int, to_list(a))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 176,
"text": [
"[5, 4, 1]"
]
}
],
"prompt_number": 176
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Lisaks - MAP ja FILTER, algarvud ning fizzbuzz"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"MAP = lambda f: lambda lst: \\\n",
" REDUCE(lambda el: PREPEND(f(el)))(NIL)(lst)\n",
" \n",
"MAP = lambda f: REDUCE(lambda el: PREPEND(f(el)))(NIL)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 62
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"SQUARE = lambda num: MULTIPLY(num)(num)\n",
"map(to_int, to_list(MAP(SQUARE)(RANGE(ONE)(SIX))))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 61,
"text": [
"[1, 4, 9, 16, 25]"
]
}
],
"prompt_number": 61
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"FILTER = lambda pred: REDUCE(lambda el: lambda rest: \\\n",
" IF(pred(el))\n",
" (PREPEND(el)(rest))\n",
" (rest))(NIL)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 80
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"map(to_int, to_list(\n",
" FILTER(lambda x: LESS_THAN_EQUAL(x)(FIVE))\n",
" (RANGE(ONE)(NINE))))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 88,
"text": [
"[1, 2, 3, 4, 5]"
]
}
],
"prompt_number": 88
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"MOD = Y(lambda rec: lambda a: lambda b: \\\n",
" IF(LESS_THAN_EQUAL(b)(a))\n",
" (lambda x: (rec(MINUS(a)(b))(b) )(x))\n",
" (a))\n",
"to_int(MOD(TEN)(FOUR))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 96,
"text": [
"2"
]
}
],
"prompt_number": 96
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"IS_PRIME = lambda num: \\\n",
" IS_EMPTY(\n",
" FILTER(lambda x: IS_ZERO(MOD(num)(x)))\n",
" (RANGE(TWO)(num)))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 112
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"to_bool(IS_PRIME(NINE))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 113,
"text": [
"False"
]
}
],
"prompt_number": 113
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"SEVEN = PLUS(TWO)(FIVE)\n",
"to_bool(IS_PRIME(SEVEN))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 115,
"text": [
"True"
]
}
],
"prompt_number": 115
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"sieve = lambda upperbound: FILTER(IS_PRIME)(RANGE(TWO)(upperbound))\n",
"map(to_int, to_list(sieve(POWER(TWO)(SIX))))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 168,
"text": [
"[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]"
]
}
],
"prompt_number": 168
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"F = TEN\n",
"I = ELEVEN = INCREMENT(TEN)\n",
"Z = TWELVE = INCREMENT(ELEVEN)\n",
"B = THIRTEEN = INCREMENT(TWELVE) \n",
"U = FOURTEEN = INCREMENT(THIRTEEN) \n",
"FIFTEEN = MULTIPLY(THREE)(FIVE)\n",
"HUNDRED = POWER(TEN)(TWO)\n",
"\n",
"ZZ = PREPEND(Z)(PREPEND(Z)(NIL))\n",
"FIZZ = PREPEND(F)(PREPEND(I)(ZZ))\n",
"BUZZ = PREPEND(B)(PREPEND(U)(ZZ))\n",
"FIZZBUZZ = PREPEND(F)(PREPEND(I)(PREPEND(Z)(PREPEND(Z)(BUZZ))))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 191
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"APPEND = lambda el: REDUCE(PREPEND)(PREPEND(el)(NIL))\n",
"\n",
"DIV = Y(lambda rec: lambda a: lambda b:\n",
" IF(LESS_THAN_EQUAL(b)(a))\n",
" (lambda x: INCREMENT(rec(MINUS(a)(b))(b))(x))\n",
" (ZERO))\n",
"\n",
"TO_DIGITS = Y(lambda rec: lambda num:\n",
" IF(LESS_THAN_EQUAL(num)(NINE))\n",
" (PREPEND(num)(NIL))\n",
" (lambda x: APPEND(MOD(num)(TEN)) (rec(DIV(num)(TEN)))(x)))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 192
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def to_string(lst):\n",
" chartable = \"0123456789FIZBU\"\n",
" codes = map(to_int, to_list(lst))\n",
" return \"\".join(chartable[x] for x in codes)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 193
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"FB = lambda num: (\n",
" IF(IS_ZERO(MOD(num)(FIFTEEN)))\n",
" (FIZZBUZZ)\n",
" (IF(IS_ZERO(MOD(num)(FIVE)))\n",
" (BUZZ)\n",
" (IF(IS_ZERO(MOD(num)(THREE)))\n",
" (FIZZ)\n",
" (TO_DIGITS(num)))))\n",
"_101 = INCREMENT(HUNDRED)\n",
" \n",
"a = MAP(FB)(RANGE(ONE)(_101))\n",
"map(to_string, to_list(a))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "pyout",
"prompt_number": 194,
"text": [
"['1',\n",
" '2',\n",
" 'FIZZ',\n",
" '4',\n",
" 'BUZZ',\n",
" 'FIZZ',\n",
" '7',\n",
" '8',\n",
" 'FIZZ',\n",
" 'BUZZ',\n",
" '11',\n",
" 'FIZZ',\n",
" '13',\n",
" '14',\n",
" 'FIZZBUZZ',\n",
" '16',\n",
" '17',\n",
" 'FIZZ',\n",
" '19',\n",
" 'BUZZ',\n",
" 'FIZZ',\n",
" '22',\n",
" '23',\n",
" 'FIZZ',\n",
" 'BUZZ',\n",
" '26',\n",
" 'FIZZ',\n",
" '28',\n",
" '29',\n",
" 'FIZZBUZZ',\n",
" '31',\n",
" '32',\n",
" 'FIZZ',\n",
" '34',\n",
" 'BUZZ',\n",
" 'FIZZ',\n",
" '37',\n",
" '38',\n",
" 'FIZZ',\n",
" 'BUZZ',\n",
" '41',\n",
" 'FIZZ',\n",
" '43',\n",
" '44',\n",
" 'FIZZBUZZ',\n",
" '46',\n",
" '47',\n",
" 'FIZZ',\n",
" '49',\n",
" 'BUZZ',\n",
" 'FIZZ',\n",
" '52',\n",
" '53',\n",
" 'FIZZ',\n",
" 'BUZZ',\n",
" '56',\n",
" 'FIZZ',\n",
" '58',\n",
" '59',\n",
" 'FIZZBUZZ',\n",
" '61',\n",
" '62',\n",
" 'FIZZ',\n",
" '64',\n",
" 'BUZZ',\n",
" 'FIZZ',\n",
" '67',\n",
" '68',\n",
" 'FIZZ',\n",
" 'BUZZ',\n",
" '71',\n",
" 'FIZZ',\n",
" '73',\n",
" '74',\n",
" 'FIZZBUZZ',\n",
" '76',\n",
" '77',\n",
" 'FIZZ',\n",
" '79',\n",
" 'BUZZ',\n",
" 'FIZZ',\n",
" '82',\n",
" '83',\n",
" 'FIZZ',\n",
" 'BUZZ',\n",
" '86',\n",
" 'FIZZ',\n",
" '88',\n",
" '89',\n",
" 'FIZZBUZZ',\n",
" '91',\n",
" '92',\n",
" 'FIZZ',\n",
" '94',\n",
" 'BUZZ',\n",
" 'FIZZ',\n",
" '97',\n",
" '98',\n",
" 'FIZZ',\n",
" 'BUZZ']"
]
}
],
"prompt_number": 194
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"a = (lambda f: (((lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda f: lambda init: lambda lst: ((lambda boolean: boolean)(((lambda pair: pair((lambda a: lambda b: a))))(lst))(init)(lambda x: f((lambda lst: ((lambda pair: pair((lambda a: lambda b: a)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(lst))(rec(f)(init)((lambda lst: ((lambda pair: pair((lambda a: lambda b: b)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(lst)))(x)))))(lambda el: ((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))(f(el))))(((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: a))((lambda a: lambda b: a))))))((lambda num: ((lambda boolean: boolean)((lambda num: num(lambda x: ((lambda a: lambda b: b)))((lambda a: lambda b: a)))(((lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda a: lambda b: ((lambda boolean: boolean)((lambda a: lambda b: ((lambda num: num(lambda x: ((lambda a: lambda b: b)))((lambda a: lambda b: a)))((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))))(b)(a)) (lambda x: (rec((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))(b) )(x)) (a))))(num)(((lambda a: lambda b: a((lambda a: lambda b: a((lambda num: lambda f: lambda x: f(num(f)(x))))(b))(b))((lambda f: lambda x: x)))((lambda f: lambda x: f(f(f(x)))))((lambda f: lambda x: f(f(f(f(f(x))))))))))) (((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))(((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))(((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))))((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))))))(((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))(((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: a))((lambda a: lambda b: a))))))))))))))) ((lambda boolean: boolean)((lambda num: num(lambda x: ((lambda a: lambda b: b)))((lambda a: lambda b: a)))(((lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda a: lambda b: ((lambda boolean: boolean)((lambda a: lambda b: ((lambda num: num(lambda x: ((lambda a: lambda b: b)))((lambda a: lambda b: a)))((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))))(b)(a)) (lambda x: (rec((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))(b) )(x)) (a))))(num)((lambda f: lambda x: f(f(f(f(f(x))))))))) (((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))))((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))))))(((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))(((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: a))((lambda a: lambda b: a)))))))))) ((lambda boolean: boolean)((lambda num: num(lambda x: ((lambda a: lambda b: b)))((lambda a: lambda b: a)))(((lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda a: lambda b: ((lambda boolean: boolean)((lambda a: lambda b: ((lambda num: num(lambda x: ((lambda a: lambda b: b)))((lambda a: lambda b: a)))((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))))(b)(a)) (lambda x: (rec((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))(b) )(x)) (a))))(num)((lambda f: lambda x: f(f(f(x))))))) (((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))(((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))(((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))((((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x)))))))))))))))))(((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: a))((lambda a: lambda b: a)))))))))) (((lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda num: ((lambda boolean: boolean)((lambda a: lambda b: ((lambda num: num(lambda x: ((lambda a: lambda b: b)))((lambda a: lambda b: a)))((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))))(num)(((lambda a: lambda b: a((lambda a: lambda b: a((lambda num: lambda f: lambda x: f(num(f)(x))))(b))(b))((lambda f: lambda x: x)))((lambda f: lambda x: f(f(f(x)))))((lambda f: lambda x: f(f(f(x)))))))) ((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))(num)(((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: a))((lambda a: lambda b: a))))) (lambda x: ((lambda el: (((lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda f: lambda init: lambda lst: ((lambda boolean: boolean)(((lambda pair: pair((lambda a: lambda b: a))))(lst))(init)(lambda x: f((lambda lst: ((lambda pair: pair((lambda a: lambda b: a)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(lst))(rec(f)(init)((lambda lst: ((lambda pair: pair((lambda a: lambda b: b)))((lambda pair: pair((lambda a: lambda b: b)))(lst))))(lst)))(x)))))((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst)))))((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))(el)(((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: a))((lambda a: lambda b: a)))))))(((lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda a: lambda b: ((lambda boolean: boolean)((lambda a: lambda b: ((lambda num: num(lambda x: ((lambda a: lambda b: b)))((lambda a: lambda b: a)))((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))))(b)(a)) (lambda x: (rec((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))(b) )(x)) (a))))(num)((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x))))))))))))) (rec(((lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda a: lambda b: ((lambda boolean: boolean)((lambda a: lambda b: ((lambda num: num(lambda x: ((lambda a: lambda b: b)))((lambda a: lambda b: a)))((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))))(b)(a)) (lambda x: ((lambda num: lambda f: lambda x: f(num(f)(x)))(rec((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))(b))(x))) ((lambda f: lambda x: x)))))(num)((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x))))))))))))))(x))))))(num)))))))(((lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda rec: lambda start: lambda end: ((lambda boolean: boolean)((lambda a: lambda b: ((lambda num: num(lambda x: ((lambda a: lambda b: b)))((lambda a: lambda b: a)))((lambda a: lambda b: b((lambda num: lambda f: lambda x: num(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)))(a))(a)(b))))(end)(start))(((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: a))((lambda a: lambda b: a))))(lambda x: ((lambda el: lambda lst: ((lambda head: lambda tail: lambda f: f(head)(tail))((lambda a: lambda b: b))((lambda head: lambda tail: lambda f: f(head)(tail))(el)(lst))))(start)(rec((lambda num: lambda f: lambda x: f(num(f)(x)))(start))(end)) )(x)))))((lambda f: lambda x: f(x)))(((lambda num: lambda f: lambda x: f(num(f)(x)))(((lambda a: lambda b: b(a))((lambda f: lambda x: f(f(f(f(f(f(f(f(f(f(x))))))))))))((lambda f: lambda x: f(f(x)))))))))\n",
"# map(to_string, to_list(a)) "
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 173
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"-----------------------------\n",
"Lisalugemist:\n",
"\n",
"* [Parser mis genereeris laiendatud avaldised](https://gist.github.com/macobo/5525312)\n",
"* [Algne inspiratsioon](http://codon.com/programming-with-nothing)\n",
"* [Lambda calculus wiki](http://en.wikipedia.org/wiki/Lambda_calculus)"
]
}
],
"metadata": {}
}
]
}
@macobo
Copy link
Author

macobo commented May 6, 2013

http://nbviewer.ipython.org/5523724

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment