Solutions to Questions Of Pattern Matching And Higher Order Functions In OCAML Assignment Solution
July 02, 2024
.png){kind=avatar}
Liam Chen
🇦🇺 Australia
Haskell
Liam Chen, a graduate of the University of Melbourne with a Bachelor's degree in Game Design, has extensive experience in creating dynamic game environments and character interactions. With over 750 assignments completed, Liam is known for his creative approach to game design and his proficiency in integrating interactive elements seamlessly.
Key Topics
- Instructions
- Requirements and Specifications
Tip of the day
News
Instructions
Objective
Write a program in Haskell to create and implement functions for manipulating trees.
Requirements and Specifications
Applying Functions to Trees Background Material
There are many possible variants of the type of binary trees introduced in the Lecture Notes.
Notice how now, the tree stores two different types of data: an element of type `a` at each fork and an element of type
`b` at each leaf.
Implementation Task
Your task is to write a haskell assignment higher-order function `applyfuns` that takes two functions `f :: a -> c` and `g :: b -> d`, as well as an element of type `Tree a b` as input and applies the first function to the values found at the forks, and the second function to the values found at the leaves. That is, implement the function:
```haskell
applyfuns :: (a -> c) -> (b -> d) -> Tree a b -> Tree c d
applyfuns = undefined
```
Screenshots of output
Source Code
-- setting the "warn-incomplete-patterns" flag asks GHC to warn you-- about possible missing cases in pattern-matching definitions{-# OPTIONS_GHC -fwarn-incomplete-patterns #-}-- see https://wiki.haskell.org/Safe_Haskell{-# LANGUAGE Safe #-}module Assessed2 (applyfuns , updateNodes , graft , elimImplications , isInCNF , toCNF , binToRose , roseToBin) whereimport Types------------------------------------------------------------------------------------------------- DO **NOT** MAKE ANY CHANGES ABOVE THIS LINE ----------------------------------------------------------------------------------------------------- {- Exercise 1 -}applyfuns :: (a -> c) -> (b -> d) -> Tree a b -> Tree c dapplyfuns _ fleaf (Leaf x) = Leaf (fleaf x) -- if leaf, apply second functionapplyfuns ffork fleaf (Fork lt x rt) = -- if fork, apply first function and recurse Fork (applyfuns ffork fleaf lt) (ffork x) (applyfuns ffork fleaf rt){- Exercise 2 -}updateNodes :: Route -> (a -> a) -> BinTree a -> BinTree aupdateNodes _ _ Empty = Empty -- if leaf, endupdateNodes [] f (Node lt x rt) = Node lt (f x) rt -- if empty route, apply to root and end-- if left, apply to this node and recurse leftupdateNodes (GoLeft:ts) f (Node lt x rt) = Node (updateNodes ts f lt) (f x) rt-- if right, apply to this node and recurse rightupdateNodes (GoRight:ts) f (Node lt x rt) = Node lt (f x) (updateNodes ts f rt){- Exercise 3 -}graft :: Rose -> [ Rose ] -> (Rose , [ Rose ])-- if leaf, append head of list, return grafted tree and tailgraft (Br []) (br:tl) = (br, tl)graft (Br brlst) ls = let (nbrs, nlst) = graftList brlst ls in -- graft nodes in list (Br nbrs, nlst) -- return new tree with the grafted nodes and the resulting list where -- graft a list of nodes graftList [] gs = ([], gs) -- if we reached the end of list, return empty list and remaining graftList (hb:tb) gs = -- if the list has more elements let (rb, lb) = graft hb gs in -- process head, save the result let (rs, rl) = graftList tb lb in -- recurse to process rest of list, save result (rb:rs, rl) -- combine head result with tail list result, return it with the remaining list{- Exercise 4 -}elimImplications :: Expr -> ExprelimImplications (Not p) = Not (elimImplications p)elimImplications (Conj p q) = Conj (elimImplications p) (elimImplications q)elimImplications (Disj p q) = Disj (elimImplications p) (elimImplications q)-- replace p-> q by ~p v qelimImplications (Implies p q) = Disj (Not (elimImplications p)) (elimImplications q)elimImplications (Var s) = Var sisInCNF :: Expr -> BoolisInCNF expr | isClause expr = True -- is cnf if it's a clause | otherwise = case expr of (Conj p q) -> isInCNF p && isInCNF q -- it's cnf if it's a conjunction of cnf's _ -> False -- else, it's not a cnf where isClause (Var _) = True -- literal is a clause isClause (Not (Var _)) = True -- negation of literal is a clause isClause (Disj p q) = isClause p && isClause q -- Clause v Clause is a clause isClause _ = False -- anything else is not a clausetoCNF :: Expr -> ExprtoCNF e = simpDistrib (simpNegations (simpDeMorgan (simpNegations (elimImplications e)))) where simpNegations (Not (Not p)) = p simpNegations (Conj p q) = Conj (simpNegations p) (simpNegations q) simpNegations (Disj p q) = Disj (simpNegations p) (simpNegations q) simpNegations x = x -- vars are not simplified simpDeMorgan (Not (Disj p q)) = Conj (Not (simpDeMorgan p)) (Not (simpDeMorgan q)) simpDeMorgan (Not (Conj p q)) = Disj (Not (simpDeMorgan p)) (Not (simpDeMorgan q)) simpDeMorgan (Not p) = Not (simpDeMorgan p) simpDeMorgan (Disj p q) = Disj (simpDeMorgan p) (simpDeMorgan q) simpDeMorgan (Conj p q) = Conj (simpDeMorgan p) (simpDeMorgan q) simpDeMorgan x = x simpDistrib (Disj p (Conj q r)) = let simpp = simpDistrib p in Conj (Disj simpp (simpDistrib q)) (Disj simpp (simpDistrib r)) simpDistrib (Disj (Conj p q) r) = let simpr = simpDistrib r in Conj (Disj (simpDistrib p) simpr) (Disj (simpDistrib q) simpr) simpDistrib (Not p) = Not (simpDistrib p) simpDistrib (Disj p q) = Disj (simpDistrib p) (simpDistrib q) simpDistrib (Conj p q) = Conj (simpDistrib p) (simpDistrib q) simpDistrib x = x{- Exercise 5 -}binToRose :: Bin -> RosebinToRose Root = Br [] -- leaf is an empty rose-- use helper to fill rose tree if root doesn't have leftbinToRose (Branch Root r) = Br (binToRosePar r []) where -- par is the current parent list of nodes binToRosePar Root par = par -- if we reached a leaf, return the list of parent nodes binToRosePar (Branch l r) par = let narch = binToRosePar r [] in -- convert right child let parch = binToRosePar l par in -- convert left child -- add current node using converted right child as its list of nodes, -- to the parent nodes after left child has been added (Br narch):parch-- else, convert directly to binary rosebinToRose (Branch l r) = binToRoseB (Branch l r) where binToRoseB Root = Br [] binToRoseB (Branch l r) = Br [binToRoseB l, binToRoseB r]roseToBin :: Rose -> BinroseToBin root | isBin root = roseToBinB root -- if is a binart, convert directly | otherwise = roseToBinSib [root] -- process as a node without siblings where roseToBinSib [] = Root -- if no more siblings, is a leaf -- if there is a node, create branch, add siblings to the left and -- children of this node to the right roseToBinSib ((Br chs):ss) = Branch (roseToBinSib ss) (roseToBinSib chs) roseToBinB (Br []) = Root roseToBinB (Br [l,r]) = Branch (roseToBinB l) (roseToBinB r) roseToBinB _ = Root isBin (Br []) = True isBin (Br [_]) = False isBin (Br (l:r:[])) = isBin l && isBin r isBin (Br _) = FalseRelated Samples
Discover our Haskell Assignment Samples for precise solutions to functional programming challenges. Covering monads, recursion, and type inference, these examples provide clear explanations and practical implementations. Perfect for students aiming to deepen their Haskell skills and excel academically with structured, educational content tailored to programming assignments.
Haskell
Word Count
4362 Words
Writer Name:Dr. Liam Patel
Total Orders:600
Satisfaction rate:
Haskell
Word Count
6608 Words
Writer Name:John Williams
Total Orders:900
Satisfaction rate:
Haskell
Word Count
5340 Words
Writer Name:Dr. Samantha Taylor
Total Orders:715
Satisfaction rate:
Haskell
Word Count
6469 Words
Writer Name:Dr. Samantha Taylor
Total Orders:715
Satisfaction rate:
Haskell
Word Count
4143 Words
Writer Name:Prof. Liam Reynolds
Total Orders:685
Satisfaction rate:
Haskell
Word Count
4466 Words
Writer Name:Nadia Dubois
Total Orders:682
Satisfaction rate:
Haskell
Word Count
6071 Words
Writer Name:Dr. Samantha Bennett
Total Orders:812
Satisfaction rate:
Haskell
Word Count
4841 Words
Writer Name:Dr. Chloe Wong
Total Orders:941
Satisfaction rate:
Haskell
Word Count
4266 Words
Writer Name:David Lee
Total Orders:764
Satisfaction rate:
Haskell
Word Count
12138 Words
Writer Name:Professor Anderson
Total Orders:700
Satisfaction rate:
Haskell
Word Count
3767 Words
Writer Name:Professor Marcus Johnson
Total Orders:600
Satisfaction rate:
Haskell
Word Count
5726 Words
Writer Name:Nadia Dubois
Total Orders:682
Satisfaction rate:
Haskell
Word Count
11881 Words
Writer Name:Professor Marcus Johnson
Total Orders:600
Satisfaction rate:
Haskell
Word Count
3752 Words
Writer Name:Dr. Chen Wang
Total Orders:521
Satisfaction rate:
Haskell
Word Count
5102 Words
Writer Name:Dr. Benjamin
Total Orders:812
Satisfaction rate:
Haskell
Word Count
7728 Words
Writer Name:Liam Chen
Total Orders:750
Satisfaction rate:
Haskell
Word Count
5512 Words
Writer Name:Dr. Chloe Wong
Total Orders:941
Satisfaction rate:
Haskell
Word Count
987 Words
Writer Name:David Lee
Total Orders:764
Satisfaction rate:
Haskell
Word Count
4978 Words
Writer Name:Professor Marcus Johnson
Total Orders:600
Satisfaction rate:
Haskell
Word Count
4716 Words
Writer Name:Professor Marcus Johnson
Total Orders:600
Satisfaction rate: