Created
February 23, 2018 03:12
-
-
Save supermacro/7f96831225f1aec68c69bdb5586f3d20 to your computer and use it in GitHub Desktop.
Elm Examples
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{- OVERVIEW ------------------------------------------------------ | |
A "Tree" represents a binary tree. A "Node" in a binary tree | |
always has two children. A tree can also be "Empty". Below I have | |
defined "Tree" and a number of useful functions. | |
This example also includes some challenge problems! | |
-----------------------------------------------------------------} | |
import Html exposing (Html, div, text) | |
import Html.Attributes exposing (style) | |
-- TREES | |
type Tree a | |
= Empty | |
| Node a (Tree a) (Tree a) | |
empty : Tree a | |
empty = | |
Empty | |
singleton : a -> Tree a | |
singleton v = | |
Node v Empty Empty | |
insert : comparable -> Tree comparable -> Tree comparable | |
insert x tree = | |
case tree of | |
Empty -> | |
singleton x | |
Node y left right -> | |
if x > y then | |
Node y left (insert x right) | |
else if x < y then | |
Node y (insert x left) right | |
else | |
tree | |
fromList : List comparable -> Tree comparable | |
fromList xs = | |
List.foldl insert empty xs | |
flatten : Tree a -> List a | |
flatten tree = | |
case tree of | |
Empty -> [] | |
Node v left right -> v :: ((flatten left) ++ (flatten right)) | |
isElement : a -> Tree a -> Bool | |
isElement needle haystack = | |
case haystack of | |
Empty -> False | |
Node v left right -> | |
v == needle || (isElement needle left) || (isElement needle right) | |
fold : (a -> b -> b) -> b -> Tree a -> b | |
fold f init tree = | |
case tree of | |
Empty -> init | |
Node v left right -> f init v | |
depth : Tree a -> Int | |
depth tree = | |
case tree of | |
Empty -> 0 | |
Node v left right -> | |
1 + max (depth left) (depth right) | |
map : (a -> b) -> Tree a -> Tree b | |
map f tree = | |
case tree of | |
Empty -> Empty | |
Node v left right -> | |
Node (f v) (map f left) (map f right) | |
treeSum : Tree Int -> Int | |
treeSum tree = | |
case tree of | |
Empty -> 0 | |
Node n left right -> n + (treeSum left) + (treeSum right) | |
-- PLAYGROUND | |
deepTree = | |
fromList [1,2,3] | |
niceTree = | |
fromList [2,1,3] | |
main = | |
div [ style [ ("font-family", "monospace") ] ] | |
[ display "depth deepTree" (depth deepTree) | |
, display "depth niceTree" (depth niceTree) | |
, display "incremented" (map (\n -> n + 1) niceTree) | |
, display "niceTree sum" (treeSum niceTree) | |
, display "deepTree sum" (treeSum deepTree) | |
, display "flatten niceTree" (flatten niceTree) | |
, display "isElement" (isElement 22 niceTree) | |
] | |
display : String -> a -> Html msg | |
display name value = | |
div [] [ text (name ++ " ==> " ++ toString value) ] | |
{----------------------------------------------------------------- | |
Exercises: | |
(1) Sum all of the elements of a tree. | |
sum : Tree number -> number | |
(2) Flatten a tree into a list. | |
flatten : Tree a -> List a | |
(3) Check to see if an element is in a given tree. | |
isElement : a -> Tree a -> Bool | |
(4) Write a general fold function that acts on trees. The fold | |
function does not need to guarantee a particular order of | |
traversal. | |
fold : (a -> b -> b) -> b -> Tree a -> b | |
(5) Use "fold" to do exercises 1-3 in one line each. The best | |
readable versions I have come up have the following length | |
in characters including spaces and function name: | |
sum: 16 | |
flatten: 21 | |
isElement: 46 | |
See if you can match or beat me! Don't forget about currying | |
and partial application! | |
(6) Can "fold" be used to implement "map" or "depth"? | |
(7) Try experimenting with different ways to traverse a | |
tree: pre-order, in-order, post-order, depth-first, etc. | |
More info at: http://en.wikipedia.org/wiki/Tree_traversal | |
-----------------------------------------------------------------} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment