{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 8. Declaring types and classes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 8.1 Type declarations" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "new name for an existing type\n", "```\n", "type String = [Char]\n", "```\n", "name of type MUST begin with upper-case letter" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [], "source": [ "type Pos = (Int,Int)\n", "type Trans = Pos -> Pos" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Type declarations cannot be recursive; so the following is not allowed:\n", "```\n", "type Tree = (Int,[Tree])\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Type declarations can be parameterized by other types:" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(10,10)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "(\"John\",\"Alice\")" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "type Pair a = (a,a)\n", "(10,10) :: Pair Int\n", "(\"John\",\"Alice\") :: Pair [Char]" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(\"John\",32),(\"Alice\",22)]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "type Assoc k v = [(k,v)]\n", "[(\"John\",32),(\"Alice\",22)] :: Assoc [Char] Int\n", "t = [(\"John\",[10,20,30]),(\"Alice\",[1,2,3])] :: Assoc [Char] [Int]" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,2,3]" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "[10,20,30]" ] }, "metadata": {}, "output_type": "display_data" }, { "ename": "", "evalue": "", "header": "MessageHeader {mhIdentifiers = [\"2225d6d9-1410-4f4c-a2a0-95263c66842d\"], mhParentHeader = Just (MessageHeader {mhIdentifiers = [\"2225d6d9-1410-4f4c-a2a0-95263c66842d\"], mhParentHeader = Nothing, mhMetadata = Metadata (fromList [(\"recordTiming\",Bool False),(\"deletedCells\",Array [String \"b05ddc0f-4f44-4209-bec6-d54771f2949f\",String \"3d18a4cc-6565-4150-907f-0f96c34d5a7d\",String \"125cb3e9-33f6-484a-9488-378a34a87b22\",String \"6c5e86a2-aa17-44ec-8ce3-6a03c773d069\",String \"a0a57ff5-2b8e-4787-9568-49d66ce41147\",String \"447b3b5b-7118-4f03-86a4-e780fea55fa9\",String \"7c783d8f-9c81-4824-8b93-62041a4d9474\",String \"7966eab5-f954-4be7-a8c2-621f262e8a4f\",String \"731b288a-584a-44a6-a58f-91c2e7d7bdad\",String \"bec6fc59-ab43-4b68-9407-5dc16dcfdb79\",String \"5dbe1361-ec34-414d-b106-dad2c4fb7169\",String \"7d249656-bde3-4c3c-bdb6-a4ed488929a6\",String \"4fcbe5dc-d3ae-4dea-9f8d-14e904649482\",String \"91607fbf-2117-4735-96a0-c7b835aced74\",String \"40d8a595-8ed2-4d1e-8e5e-e024d571246d\",String \"9c2e168f-694a-4a70-af7f-2f1bead8b69c\",String \"2c10189c-ab34-431c-be56-63b0e15a67e9\",String \"11a02f12-9a91-46ef-8ad3-0f719def7956\",String \"70b996f0-0ce7-4d64-a560-e9f7e0240f33\",String \"859fb5be-1e56-4f5e-8e14-cd1be5bbaa6a\"]),(\"cellId\",String \"ad548616-701e-4582-b582-cb3f01c5a70a\")]), mhMessageId = UUID {uuidToString = \"f27cef04-ed56-4913-a76e-7e2a2ffcac32\"}, mhSessionId = UUID {uuidToString = \"2225d6d9-1410-4f4c-a2a0-95263c66842d\"}, mhUsername = \"\", mhMsgType = ExecuteRequestMessage, mhBuffers = []}), mhMetadata = Metadata (fromList []), mhMessageId = UUID {uuidToString = \"ed06d74f-5e86-4677-9539-2e07364b83bc\"}, mhSessionId = UUID {uuidToString = \"2225d6d9-1410-4f4c-a2a0-95263c66842d\"}, mhUsername = \"\", mhMsgType = ExecuteErrorMessage, mhBuffers = []}", "output_type": "error", "traceback": [ "Prelude.head: empty list" ] } ], "source": [ "find :: Eq k => k -> Assoc k v -> v\n", "find k t = head [v | (k',v) <- t, k' == k]\n", "\n", "find \"Alice\" t\n", "find \"John\" t\n", "find \"James\" t" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 8.2 Data declarations" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A completely new type can be defined using the data mechanism of Haskell\n", "```\n", "data Bool = False | True\n", "```\n", "Here, | is read as \"or\" and the values are \"constructors\"; constructors MUST begin with upper-case letters" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
Use foldl
Found:
moves [] p = p\n", "moves (m : ms) p = moves ms (move m p)
Why Not:
moves ms p = foldl (flip move) p ms
" ], "text/plain": [ "Line 11: Use foldl\n", "Found:\n", "moves [] p = p\n", "moves (m : ms) p = moves ms (move m p)\n", "Why not:\n", "moves ms p = foldl (flip move) p ms" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "-- another example\n", "data Move = North | South | East | West deriving Show\n", "\n", "move :: Move -> Pos -> Pos\n", "move North (x,y) = (x,y+1)\n", "move South (x,y) = (x,y-1)\n", "move East (x,y) = (x+1,y)\n", "move North (x,y) = (x-1,y)\n", "\n", "moves :: [Move] -> Pos -> Pos\n", "moves [] p = p\n", "moves (m:ms) p = moves ms (move m p)\n", "\n", "rev :: Move -> Move\n", "rev North = South\n", "rev South = North\n", "rev East = West\n", "rev West = East" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### another example" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Constructors in data declarations may have arguments" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [], "source": [ "data Shape = Circle Float | Rect Float Float deriving (Eq,Ord,Show)" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [], "source": [ "square :: Float -> Shape\n", "square n = Rect n n" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [], "source": [ "area :: Shape -> Float\n", "area (Circle r) = pi * r^2\n", "area (Rect x y) = x * y" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "28.274334" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "area (Circle 3)" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8.0" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "area (Rect 2 4)" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "data": { "text/html": [ "Circle :: Float -> Shape" ], "text/plain": [ "Circle :: Float -> Shape" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ ":type Circle" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "data": { "text/html": [ "Rect :: Float -> Float -> Shape" ], "text/plain": [ "Rect :: Float -> Float -> Shape" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ ":type Rect" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So, in fact the constructors are actually constructor \"functions\", but are different from ordinary functions in that these are fully evaluated and are just pieces of data" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Circle 3.0" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "Rect 1.0 4.0" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "Circle 3\n", "Rect 1.0 4.0" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-1.0" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "negate 1.0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### parameterized data declarations" ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [], "source": [ "data Maybe a = Nothing | Just a deriving Show" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nothing represents \"failure\" and Just a represents \"success\"" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [], "source": [ "safediv :: Int -> Int -> Maybe Int\n", "safediv _ 0 = Nothing\n", "safediv m n = Just (m `div` n)\n", "\n", "safehead :: [a] -> Maybe a\n", "safehead [] = Nothing\n", "safehead xs = Just (head xs)" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Nothing" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "Just 2" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "Nothing" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "Just 1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "safediv 12 0\n", "safediv 12 5\n", "safehead []\n", "safehead [1,2,3]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 8.3 Newtype declaration" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If a new type has a single constructor with a single argument, we can define it as follows:\n", "```\n", "newtype Nat = N Int\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The programmer will have to ensure that no negative numbers are assigned as values to variable sof Nat type" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So, the question arises on the differences between the following three:\n", "```\n", "newtype Nat = N Int\n", "type Nat = Int\n", "data Nat = N Int\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As the name suggests, newtype creates a new type! whereas type creates an alias for another type. So, in \n", "```\n", "newtype Nat = N Int\n", "```\n", "Nat and Int are two different types. So, values cannot be interchangeably used. But in \n", "```\n", "type Nat = Int\n", "```\n", "Nat is another name for Int.\n", "\n", "The main difference between newtype and data declaration is efficiency in implementation. In a newtype after compile-time checks are made, the compiler would substitute the types at run-time. So, no new constructors need be called at run-time. Whereas in a data declaration, this is not so." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 8.4 Recursive types" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "New types declared vis data or newtype mechanisms can be recursive." ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [], "source": [ "data Nat = Zero | Succ Nat deriving Show" ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Zero" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "Succ Zero" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "Succ (Succ Zero)" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "Succ (Succ (Succ Zero))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "Zero\n", "Succ Zero\n", "Succ (Succ Zero)\n", "Succ (Succ (Succ Zero))" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [], "source": [ "nat2int :: Nat -> Int\n", "nat2int Zero = 0\n", "nat2int (Succ n) = 1 + nat2int n\n", "\n", "int2nat :: Int -> Nat\n", "int2nat 0 = Zero\n", "int2nat n = Succ (int2nat (n-1))" ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "nat2int (Succ (Succ (Succ Zero)))" ] }, { "cell_type": "code", "execution_count": 58, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Succ (Succ (Succ (Succ Zero)))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "int2nat 4" ] }, { "cell_type": "code", "execution_count": 59, "metadata": {}, "outputs": [], "source": [ "add :: Nat -> Nat -> Nat\n", "add m n = int2nat (nat2int m + nat2int n)" ] }, { "cell_type": "code", "execution_count": 60, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "nat2int (add (Succ (Succ Zero)) (Succ (Succ (Succ Zero))))" ] }, { "cell_type": "code", "execution_count": 61, "metadata": {}, "outputs": [], "source": [ "add2 :: Nat -> Nat -> Nat\n", "add2 Zero n = n\n", "add2 (Succ m) n = Succ (add2 m n)" ] }, { "cell_type": "code", "execution_count": 62, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "nat2int (add2 (Succ (Succ Zero)) (Succ (Succ (Succ Zero))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "```\n", " add2 (Succ (Succ Zero)) (Succ Zero)\n", "= Succ (add2 (Succ Zero) (Succ Zero))\n", "= Succ (Succ (add2 Zero (Succ Zero)))\n", "= Succ (Succ (Succ Zero))\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### list structure" ] }, { "cell_type": "code", "execution_count": 63, "metadata": {}, "outputs": [], "source": [ "data List a = Nil | Cons a (List a)" ] }, { "cell_type": "code", "execution_count": 64, "metadata": {}, "outputs": [], "source": [ "len :: List a -> Int\n", "len Nil = 0\n", "len (Cons _ xs) = 1 + len xs" ] }, { "cell_type": "code", "execution_count": 65, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "len (Cons 10 (Cons 20 (Cons 30 Nil)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### binary tree structure" ] }, { "cell_type": "code", "execution_count": 66, "metadata": {}, "outputs": [], "source": [ "data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving Show" ] }, { "cell_type": "code", "execution_count": 67, "metadata": {}, "outputs": [], "source": [ "t :: Tree Int\n", "t = Node (Node (Leaf 1) 3 (Leaf 4)) 5 \n", " (Node (Leaf 6) 7 (Leaf 9))" ] }, { "cell_type": "code", "execution_count": 68, "metadata": {}, "outputs": [], "source": [ "-- not assuming a binary search tree\n", "occurs :: Eq a => a -> Tree a -> Bool\n", "occurs x (Leaf y) = x == y\n", "occurs x (Node l y r) = x == y || occurs x l || occurs x r" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "False" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "occurs 6 t\n", "occurs 2 t" ] }, { "cell_type": "code", "execution_count": 70, "metadata": {}, "outputs": [], "source": [ "flatten :: Tree a -> [a]\n", "flatten (Leaf x) = [x]\n", "flatten (Node l x r) = flatten l ++ [x] ++ flatten r" ] }, { "cell_type": "code", "execution_count": 71, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,3,4,5,6,7,9]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "flatten t" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "-- assuming a binary search tree\n", "occurs :: Ord a => a -> Tree a -> Bool\n", "occurs x (Leaf y) = x == y\n", "occurs x (Node l y r) \n", " | x == y = True\n", " | x < y = occurs x l\n", " | otherwise = occurs x r" ] }, { "cell_type": "code", "execution_count": 72, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "False" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "occurs 6 t\n", "occurs 2 t" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### concluding remark regarding Tree\n", "\n", "Trees can come in various forms:\n", "\n", "- binary trees with data only in leaves\n", "- binary trees with data only in interior nodes\n", "- binary trees with data of different types in leaves vs interior nodes\n", "- general trees (more than 2 child nodes)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "```\n", "data Tree a = Leaf a | Node (Tree a) (Tree a)\n", "data Tree a = Leaf | Node (Tree a) a (Tree a)\n", "data Tree a b = Leaf a | Node (Tree a b) b (Tree a b)\n", "data Tree a = Node a [Tree a]\n", "```" ] } ], "metadata": { "kernelspec": { "display_name": "Haskell", "language": "haskell", "name": "haskell" }, "language_info": { "codemirror_mode": "ihaskell", "file_extension": ".hs", "name": "haskell", "pygments_lexer": "Haskell", "version": "8.6.5" } }, "nbformat": 4, "nbformat_minor": 4 }