{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Berekening van een polynoom in Elm"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In de docentenworkshop van 10 juni 2020 behandeld."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We willen functies zoals $x^2 + 3x + 1$ uitrekenen met Elm. In de wiskunde noemt men zoiets een *polynoom*. De som van een machten van $x$, evt. vermenigvuldigd met een factor, een zogenaamde *coëfficiënt*. \n",
"\n",
"In de Elm-REPL notebooks is het symbool ^ voor machtsverheffing niet beschikbaar. Dus we definiëren eerst een functie **pow** die machtsverheffen uitvoert. "
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"<function> : number -> number1 -> number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"pow a b = \\\n",
" if b <= 0 then 1 \\\n",
" else a * pow a (b-1)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"1 : number\n",
"1024 : number\n",
"1000000 : number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"pow 10 0\n",
"pow 2 10\n",
"pow 10 6"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Met powerfunctie\n",
"Eerste stap is gewoon een functie die bovengenoemde polynoom uitrekent."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"<function> : number -> number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly0 x = \\\n",
" pow x 2 + 3 * x + 1"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"11 : number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly0 2 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We willen nu een functie die werkt voor alle polynomen werkt. Een polynoom is bepaald door een lijst van coëfficiënten. Iedere coëfficiënt hoort bij een macht van x. Als een macht er niet in voorkomt, zetten we een 0 in de lijst. \n",
"\n",
"Dus [1, 3, 1] stelt $x^2 + 3x + 1$ voor.\n",
"En [2, 0, 3, 0, 5] stelt $2x^4 + 3x^2 + 5$ voor. (Let op! straks draaien we de volgorde om.)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"<function> : List number -> number -> number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly1 coefs x = \\\n",
" case coefs of \\\n",
" [] -> 0 \\\n",
" c :: cs -> c * pow x (List.length cs) + poly1 cs x"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"11 : number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly1 [1,3,1] 2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Merk op dat de functie *poly0* gelijk is aan *poly1 [1,3,1]* (laat het argument *x* weg, en je hebt een functie)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Zonder powerfunctie\n",
"\n",
"We zien dat steeds de macht van x moet worden uitgerekend. Eerst $x^4$, dan $x^3$, enzovoort. Dat kan handiger. Als je het in omgekeerde volgorde zou doen, hoef je alleen maar steeds de vorige macht te nemen en die met x te vermenigvuldigen. We moeten dan wel die vorige macht onthouden. Dat kan met een extra parameter, lastpowerofx. (Verderop zullen we die weer lozen.)\n",
"\n",
"\n",
"En verder nemen we aan dat de lijst coëfficiënten nu andersom geordend is en eindigt met de hoogste macht van x."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"<function> : List number -> number -> number -> number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly2 coefs lastpowerofx x = \\\n",
" case coefs of \\\n",
" [] -> 0 \\\n",
" c::cs -> c * lastpowerofx + poly2 cs (lastpowerofx * x) x"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"11 : number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly2 [1,3,1] 1 2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Steeds de startwaarde 1 voor lastpowerofx aangeven is wat onhandig. Daarom definiëren we een niet-recursieve functie *poly3* die de recursieve *poly2* aanroept met de goede startwaarde. Dit is een patroon dat je vaak ziet bij recursieve functies. "
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"<function> : List number -> number -> number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly3 coefs x = poly2 coefs 1 x "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"of (de x aan beide kanten kun je weglaten)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"<function> : List number -> number -> number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly3 coefs= poly2 coefs 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Zonder lastpowerofx"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Het kan nog iets strakker. Kijk naar het polynoom $5 + 4x + 3x^2 + 2x^3$. Je kunt dat ook schrijven als $5 + x(4 + x(3 + x(2+0)))$. \n",
"Er komt precies hetzelfde uit, maar je vermenigvuldigt niet met *machten* van $x$, maar alleen met $x$. Als we deze berekening gebruiken in onze poly-functie hoeven we dus geen macht van $x$ te bewaren en kunnen we de parameter *lastpowerofx* weer lozen.\n",
"\n",
"Deze manier om een polynoom te berekenen heet het *Hornerschema*, naar de Britse wiskundige William Horner."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"<function> : List number -> number -> number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly4 coefs x = \\\n",
" case coefs of \\\n",
" [] -> 0 \\\n",
" c::cs -> c + x * (poly4 cs x)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"11 : number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly4 [1,3,1] 2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Pointfree"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(Niet in de workshop) We kunnen nog een stap maken, waarbij we een *pointfree* definitie van de functie geven. Het is een stijl in het functioneel programmeren waarbij je zoveel mogelijk functies met behulp van andere functies definieert en niet met losse waarden. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### List.foldr"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Als je de som van de elementen van een lijst wilt uitrekenen kun je dat als volgt, niet pointfree, doen."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"<function> : List number -> number\n",
"10 : number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"som xs = \\\n",
" case xs of \\\n",
" [] -> 0 \\\n",
" y::ys -> y + som ys\n",
"\n",
"som [1,2,3,4]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Je ziet dat in de functie het eerste element van de lijst wordt afgepeld en gebruikt wordt in de optelling. Je zou dat element een punt kunnen noemen en deze functie is daarom niet pointfree. Maar met behulp van de functie *foldr* kunnen we dit anders aanpakken. De functie *foldr* neemt net als map een functie en past die toe op alle elementen van de lijst. Maar map gebruikt een functie met één parameter en het resultaat is weer een lijst. Bij *foldr* gebruik je een functie met twee parameters, bijvoorbeeld optellen, en die wordt steeds toegepast op een element van de lijst en het resultaat dat je tot dan toe had. De lijst wordt als het ware opgevouwen tot één getal, de som in dit geval. Je moet ook nog de startwaarde geven, deze waarde krijg je er ook uit als foldr op een lege lijst werkt. Hieronder zie je hoe je *foldr* toepast. Operaties als *foldr* heten ook wel *reduce*-operaties, omdat ze een lijst terugbrengen tot één waarde.\n",
"\n",
"Als je in Elm de functie van het optellen nodig hebt, schrijf je **(+)**."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"10 : number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"List.foldr (+) 0 [1,2,3,4]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Alle elementen *vermenigvuldigen* gaat net zo makkelijk. Je moet wel een andere startwaarde gebruiken."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"24 : number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"List.foldr (*) 1 [1,2,3,4]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"De r in de naam *foldr* staat voor right, omdat de berekening rechts begint. Hij rekent dit uit als 1+(2+(3+(4+0))). Er is ook een variant *foldl* die links begint. Bij optellen komt er hetzelfde uit, maar bij andere functies kunnen *foldr* en *foldl* wel verschillende uitkomsten geven."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Berekening met foldr\n",
"\n",
"We passen nu *foldr* toe om de polynoom-berekening pointfree te maken. We moeten daarvoor de functie bedenken die we aan *foldr* gaan meegeven. (Bij de som-berekening was dat de +.) Kijk daarom naar de recursieve cases van de functies *som* en *poly4*:\n",
"\n",
"y::ys -> y + som ys\n",
"\n",
"y::ys -> y + x * (poly4 x ys)\n",
"\n",
"In de som-functie worden de head van de lijst, y, en de tail met daarop de recursieve call, som ys, gecombineerd met de +-operator. Bij poly4 is het ietsje ingewikkelder: de tail met recursieve call (inclusief de extra parameter x) wordt eerst met x vermenigvuldigd en dan pas opgeteld bij de head. De functie die we nodig hebben in plaats van de plus is dus (bijna): *maaldanplus a b = a + x * b*. Maar omdat x moet kunnen variëren, moet die als paramter meegegeven worden en krijg je de volgende functie."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"<function> : number -> number -> number -> number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"maaldanplus x a b = a + x * b"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"En de nieuwe polynoomfunctie wordt:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"<function> : List number -> number -> number\n",
"11 : number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly5 coefs x = List.foldr (maaldanplus x) 0 coefs\n",
"poly5 [1,3,1] 2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"De functie *maaldanplus* hoeft niet per se apart gedefinieerd te worden. We kunnen haar ook als *lambda-expressie* meegeven. Omdat *x* op die plek bekend is, hebben we die niet als parameter van de lambda-functie nodig. \n",
"\n",
"Zo kunnen we de hele polynoomberekening in één regel definiëren."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"<function> : List number -> number -> number\n",
"11 : number\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"poly6 coefs x = List.foldr (\\a -> \\b -> a + x * b) 0 coefs\n",
"poly6 [1,3,1] 2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Elm REPL",
"language": "",
"name": "defbu_elm_repl_kernel"
},
"language_info": {
"codemirror_mode": "elm",
"file_extension": ".elm",
"mimetype": "text/x-elm",
"name": "elm"
}
},
"nbformat": 4,
"nbformat_minor": 2
}