This is a course page of
David Casperson
Associate Professor
Computer Science
University of Northern British Columbia

CPSC 370: Functional and Logic Programming ( )

Questions Pending.

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

Questions Due.

  1. Explain why const is a legitimate function to use for building a semigroup.
  2. Given “data Pair a = Px a a”, define
    1. Functor,
    2. Foldable, and
    3. Applicative
    instances for Pair.
  3. 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.

  4. 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?
  5. 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.)
  6. 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.
  7. 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.)
  1. 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.)
  2. Redo the previous question using foldl and no explicit tail-recursiion.
  3. 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.
  4. 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.
  1. 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?
  2. (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.
  1. Attempt Sets and Currying (self-check) on the Fall 370 2022 page
  2. 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]]
  1. 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]).
  2. 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.
  1. 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?
  2. 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 ?
  1. Install Haskell on your computer. Tell me how you did this, including Haskell version, and the operating system for your computer.
  2. 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. 😎)
  3. There are two CPSC 141-like ∀∃ statements that formally define what a function is. What are they? Which one defines a partial function?
  4. What are the inclusion relations between partial functions, functions, and relations?

Home page Semesters Site Map
go back Fall 2022 go forward
2024-12 other links

Java
CPSC 200 [Other years]
CPSC 370 [Other years]
Homework
David’s Schedule

UNBC Undergraduate Calendar
Dates
Computer Science (BSc)
Regulations

fall-2024