CPSC 370: Functional and Logic Programming ( Fall 2011 Fall 2012 Fall 2013 Fall 2015 Fall 2016 Fall 2017 Fall 2018 Fall 2019 Fall 2022 )

from 2022-03-26

17. Give the types of the following predefined identifiers.
    1. undefined
    2. error
    3. flip where flip f x y = f y x
    4. const where const x y = x
    5. const False
    6. id where id x = x
    7. curry where curry f x y = f(x,y)
    8. >uncurry where uncurry f (x,y) = f x y (Thiw is also question 16.)

18. A combinator is a function that depends on nothing other than its arguments. There are a number of combinators built in to Haskell, as illustrated by the last question.

    Another thoeretically important combinator is the mu or Y combinator.

    1. What is the type of mu where mu f x = f (mu f) x?
    2. Suppose that we have a datatype
       data W a b = Wx(W a b -> a -> b)
       (a) what is the type of ww where ww f (Wx g) x = f (g (Wx g)) x?
       (b) what is the type of mu2 where mu2 f x = ww f (Wx (ww f)) x?

    Note that the definition of mu2 only involves recursion in that it uses the W data type. There is a theorem that says that in a typed language like Haskell, you minimally need to use a recursive data type to define mu or mu2.

    In Scheme you can just write
    (define ((w f g) x) ((f (g g)) x).
    (there are three parts of this question that actually need answers.)

19. (This question is optional. It relates to the purpose of mu2.)
    1. What is the type of factFact where
       

       factFact fact n = if (n==(0::Int)) 
               then 1
               else toInteger n * fact(n-1);

       ?
    2. Is factFact recursive? Answer No.
    3. Why not?
    4. Compute the type and value of

       • factFact udefined 0

       • factFact udefined 1

       • (factFact . factFact $ udefined) 1

       • (factFact . factFact $ udefined) 2

       • (factFact . factFact . factFact $ udefined) 2

       • mu2 factFact 

         (do not worry overly about the value above.)

       • mu2 factFact 5

    5. How much recursion do we need?
20. `The type and value of “empty” data structures are often confusing. Be sure that you understand the following:
    1. What are the type and value of []?
    2. What are the type and value of drop 3 "cat"?
    3. What are the type and value of drop 3 ["cat"]?
    4. What is []==drop 3 "cat"?
    5. What happens with drop 3 ["cat"]==drop 3 "cat"?
21. Data types with more type than value can lead to paradoxical (but currect) functor, applicative, monad, foldable, and traversable instances. Consider

    data VeryEmpty a = Void

    This has Functor, Applicative, Monad, Foldable, and Traversable instances. (Some of these can be guessed from the definitions for the Nothing case of Maybe.)

    Define these instances. Be sure to test your code. It may be helpful to use

    data VeryEmpty a = Void deriving Show

22. In “SWI Prolog” what is SWI? and at what University would you find it?
23. What does Prolog stand for?

from 2022-01-07

5. Write a better cheat-sheet for Haskell. (like the Haskell Syntax Cheat Sheet on the 370 page).

7. Write a cheat-sheet for Prolog.

from 2022-03-01

13. Make the Tree a type defined by

    data Tree a
      = EmptyTree
      | Node a (Tree a) (Tree a)
          

    have a Foldable instance.
14. Make the Tree a type defined by

    data Tree a
      = EmptyTree
      | Node a (Tree a) (Tree a)
          

    have a Traversable instance.
15. 1. What is the type of the expression \ mm -> do { m <- mm ; m } ?
    2. Expandl the do-block and make this as pointless as possible.
    3. What natural transformation is this?

from 2022-03-04

16. What is the type of uncurry where
    uncurry f (a,b) = f a b
    ?

    What does uncurry do?

9. With regard to “Currying”, who is Moses?

10. For the “Tree a” discussed in class, write a continuation-passing style tail-recursive algorithm to mirror a tree.

    “Defunctionalize” your continuations.

    What is an upper bound on the size of your continuations?

from 2022-02-07

11. foldr has a leftist cousin foldl defined by

    foldl f a [] = a      
    foldl f a (x:xs) = foldl f (f a x) xs
          

    1. What is the type of foldl? How can you deduce this without using ghci :type?
    2. foldl can be written in terms of foldr

       foldl f a xs = foldr (g f) id xs a where 
         g …
             

       What is the type of g?

       Write a definition for g.

       How “pointless” can you make g?

1. There are two CPSC 141-like ∀∃ statements that formally define what a function is. What are they? Which one defines a partial function?
2. What are the inclusion relations between partial functions, functions, and relations?
3. Install Haskell on your computer. Tell me how you did this, including Haskell version, and the operating system for your computer.
4. 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. 😎)

6. What is the connection between Haskell and “currying” a function?

8. A very preliminary sketch of how to write an Integer to String function can be found on the Blacboard site.

   Complete the code, or write your own from scratch, to provide a function to convert integers up to ??? into strings.