This is a course page of David Casperson |
|
…can be found at ./370-homework-pending.php .
const
is a legitimate function to use
for building a semigroup.
data Pair a = Px a a
”, define Functor
,Foldable
, andApplicative
Pair
.
Functions whose domain and co-domain are the same form a monoid
under composition and the identity function. Functions from a
set back to itself are sometimes called endo-morphisms, which
explains the name of the newtype,
newtype Endo a = Endo { appEndo :: a -> a }
Show how to define the Semigroup
and Monoid
instances for Endo a
.
h :: Int -> String -> String h i s = show i ++ "!" ++ s
Endo . h
a function with a monoid co-domain?
kk = foldMap (Endo . h) [3, 19, 41]
. What
is the type of kk
?
appEndo kk "???"
?
foldr h "???" [3, 19, 41]
?
foldr
using
only foldMap
?
data PointType = Point instance Semigroup PointType where (<>) = const instance Monoid PointType where mempty = Pointdetermine if this is a legitimate mathematical monoid. (yes, this example is perverse.)
isBST :: (Ord a) => Tree a -> Bool
that determines if a tree is a BST.
[5, 3, 1, 2, 4, 6, 7
must come from the tree
Node 5 (Node 3 (Node 1 ET (Node 2 ET ET)) 4) (Node 6 ET (Node 7 ET ET))Write a function
prefixToBST :: (Ord a) => [a] -> Tree a
that converts a prefix traversal of a BST back into a tree.
(The function span
may be useful.)
foldl
and no
explicit tail-recursiion.
data Tree a = ET | Node a (Tree a) (Tree a)Write an efficient tail-recursive function
infixToList :: Tree a -> [a]
The following wording revised
That is,infixToList . makeTree
should be the
identity function on lists, and
makeTree . infixToList
should return a tree with the same nodes in the same infix
order, but possibly reshaped.
Tree a
type as above, write
an efficient tail-recursive function subTrees :: Tree a -> [Tree a]that returns a list of the non-empty subtrees of a tree. To be more precise, the list does the tree itself, but does not contain
ET
.
Read Chapter 5 of Learn You a Haskell for Great Good, in particular I Fold You So.
From Lipovača's point of view Chapter 5 is about Currying and
how functions can pass and return functions. There is
another important idea in this chapter, which is that you can
often avoid explicitly writing recursion, by using a
function like
map
or
filter
.
The most important general purpose tool is foldr
(foldr
is an example of a catamorphism,
which is to say that it is somehow special with respect to lists).
The point of this exercise is to explore ways that functions
on lists can be written using
map
filter
foldl
and
foldr
to avoid explicit recursion.
Answer the following questions
sum . map (const 1)
?
foldl
(flip (:))
[]
do?
foldr (:) []
do?
(The previous question continued) Answer the following questions
gertrude
defined by gertrude f = foldr ((:).f) []
?
gertrude
do?
Write filter
using foldr
.
Here are some hints.
If
myFilter :: (a -> Bool) -> [a] -> [a]
myFilter p xs = foldr (helper p) [] xs
where helper p z zs = …
what are the types involved? That is, what are the types of
helper
,
p
,
z
,
zs
, and the right hand side?
The right hand side likely involves
an if
-expression.
What decision needs to be made?
What is the then
-expression?
What is the else
-expression?
unweave
function avoiding
explicit recursion by
using foldr
.
Mathematically, a function is a set of pairs with extra
conditions. In Haskell, it is
often more convenient to work with lists of pairs.
Which of the lists below represent a function from
[1 .. 20]
to
[1 .. 20]
?
Which of these represent a partial function, but not a function?
[((n+1)`div`2,n) | n <- [ 1..20]]
[(n,(n+1)`div`2) | n <- [ 1..20]]
[(n-21,n`div`2) | n <- [22..40]]
interleave
that takes two lists
and produces a single list that alternates between elements.
For instance
interleave [1,2,4] [7,8]
is
[1,7,2,8,4]
.
interleave [7,8] [1,2,4]
is
[7,1,8,2,4]
.
interleave [1,3 ..] [6,8 ..]
is
[1,6,3,8
…]
.
take 7 $ interleave [1,3 ..] [6,8 ..]
[1,6,3,8,5,10,7]
).
unweave
that is an approximate
inverse to interleave
. That is if
(xs,ys) = unweave zs
then
interleave xs ys
should be equal to zs
.
['k' .. 'p']
? Int
s using the
function fromEnum
.
fromEnum 'é'
? fromEnum True
?
There is also a character specific function
ord
but it needs to be imported
from Data.Char
.
Do import qualified Data.Char as Char
.
Char.ord 'é'
? Char.ord True
? ghci
:type
function determine
preciese answers to the following questions.
'k'
? ['k' .. 'p']
? fromEnum 'é'
? fromEnum
?
With import qualified Data.Char as Char
.
Char.ord 'é'
? Char.ord
? Fall 2022 | ||
2024-12 |
fall-2024