Lists

(This is a post for CS320 Boston University.)

This is a page for most commonly seen methods about a functional list (in ATS). And this is in Haskell.

Here are some commonly seen ones:

• head takes a list, returns the first element.
• last takes a list, returns the last element.
• tail takes a list, returns it without the first element.
• take takes the beginning n elements of a list.
• drop drops the beginning n elements and returns the rest.
• zip zips two (or more) lists into a list of pairs (or tuples).
• map applies a function to each element of the list to get another list.
• fold aggregates a list into a value by applying a binary function iteratively.

Please implement the following functions.

implement main () = print "Hello World!"

datatype intlist =
    | ilist_cons of (int, intlist)
    | ilist_nil of ()

datatype intintlist = 
    | iilist_cons of ((int, int), intintlist)
    | iilist_nil of ()


extern fun zip (xs: intlist, ys: intlist): intintlist
extern fun sum (xs: intlist): int
extern fun reverse (xs: intlist): intlist
extern fun map (f: int -> int, xs: intlist): intlist

extern fun addtwo (x: int): int
implement addtwo (x) = x + 2

A possible solutions:

implement zip (xs, ys) = 
    case+ xs of 
    | ilist_nil () => iilist_nil ()
    | ilist_cons (x, xs) => 
        case+ ys of 
        | ilist_nil () => iilist_nil ()
        | ilist_cons (y, ys) => iilist_cons ((x, y), zip (xs, ys))

implement sum (xs) = case+ xs of
    | ilist_cons (x, xs) => x + sum (xs)
    | ilist_nil () => 0

implement reverse (xs) = let
    fun do_reverse (xs: intlist, ys: intlist): intlist = 
        case+ xs of 
        | ilist_cons (x, xs) => do_reverse (xs, ilist_cons (x, ys))
        | ilist_nil () => ys
in 
    do_reverse (xs, ilist_nil ())
end

implement map (f, xs) = case+ xs of
    | ilist_cons (x, xs) => ilist_cons (f (x), map (f, xs))
    | ilist_nil () => ilist_nil ()

extern fun print_ilist (xs: intlist): void
implement print_ilist (xs) = case+ xs of 
    | ilist_cons (x, xs) => () where { 
        val () = fprint! (stdout_ref, x, " ")
        val () = print_ilist (xs)
        }
    | ilist_nil () => ()

extern fun print_iilist (xs: intintlist): void
implement print_iilist (xs) = case+ xs of 
    | iilist_cons ((x,y), xs) => () where { 
        val () = fprint! (stdout_ref, "(", x, ",", y, ") ")
        val () = print_iilist (xs)
        }
    | iilist_nil () => ()