CPSC 370: Functional and Logic Programming ( )

Questions Pending.

…can be found at ./370-homework-pending.php .

Questions Due.

Due 2022-12-01

Explain why const is a legitimate function to use for building a semigroup.
Given “data Pair a = Px a a”, define
1. Functor,
2. Foldable, and
3. Applicative
instances for 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.
Suppose that we define
```
  h :: Int -> String -> String
  h i s = show i ++ "!" ++ s
```
1. why is Endo . h a function with a monoid co-domain?
2. Let kk = foldMap (Endo . h) [3, 19, 41]. What is the type of kk?
3. What is the value of appEndo kk "???"?
4. What is the value of foldr h "???" [3, 19, 41]?
5. Can you write a definition of foldr using only foldMap?

Given

  data PointType = Point
  instance Semigroup PointType where 
    (<>) = const
  instance Monoid PointType where
    mempty = Point

determine if this is a legitimate mathematical monoid. (yes, this example is perverse.)

A binary tree is a Binary Search Tree if an inorder traversal (see question 16) visits elements in increasing order. Write a function isBST :: (Ord a) => Tree a -> Bool that determines if a tree is a BST.
For a Binary Search Tree, the tree can be reconstructed from a list containing the pre-order traversal of its node values. For instance the pre-order list [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.)

Due 2022-11-09

Write an explicit tail-recursive function to compute the maximum value of a non-empty list (N.B. maximum does this, and is part of the Prelude. Write your own function that avoids using the bultin maximum.)
Redo the previous question using foldl and no explicit tail-recursiion.
For the type
```
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.
For the same 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.

Due 2022-11-07

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
1. What is another name for the function
  sum . map (const 1) ?
2. What does the function foldl (flip (:)) [] do?
3. What does the function foldr (:) [] do?
(The previous question continued) Answer the following questions
1. What is the type of the function gertrude defined by
  gertrude f = foldr ((:).f) [] ?
2. What does the function gertrude do?
3. 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?
4. Redefine your unweave function avoiding explicit recursion by using foldr.

Due 2022-11-04

Attempt Sets and Currying (self-check) on the Fall 370 2022 page
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?
1. [((n+1)`div`2,n) | n <- [ 1..20]]
2. [(n,(n+1)`div`2) | n <- [ 1..20]]
3. [(n-21,n`div`2) | n <- [22..40]]

Due 2022-10-07

Write a function 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…].
Beware that attempting to print an infinite list (naturally) gets stuck in an infinite loop. However,
- take 7 $ interleave [1,3 ..] [6,8 ..]
  should work (and produce [1,6,3,8,5,10,7]).
Write a function unweave that is an approximate inverse to interleave. That is if
(xs,ys) = unweave zs then interleave xs ys should be equal to zs.

Due 2022-09-30

In Haskell, strings are lists of characters, and charcters are normally typed between single quotation marks.
1. What is the value of ['k' .. 'p']?
Characters can be converted to Ints using the function fromEnum.
1. What is the value of fromEnum 'é'?
2. What is the value of 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.
1. What is the value of Char.ord 'é'?
2. What is the value of Char.ord True?
Using the ghci :type function determine preciese answers to the following questions.
1. What is the type of 'k' ?
2. What is the type of ['k' .. 'p']?
3. What is the type of fromEnum 'é'?
4. What is the type of fromEnum?
With import qualified Data.Char as Char.
1. What is the type of Char.ord 'é'?
2. What is the type of Char.ord ?

Due 2022-09-28

Install Haskell on your computer. Tell me how you did this, including Haskell version, and the operating system for your computer.
Thera are not a lot of IDEs for Haskell. If you find one that you intend to use, tell me what it is. Otherwise, tell me what your favourite generic code-editing application is. (All choices other than emacs are wrong. 😎)
There are two CPSC 141-like ∀∃ statements that formally define what a function is. What are they? Which one defines a partial function?
What are the inclusion relations between partial functions, functions, and relations?