EOPL - 1.2.4 - Exercise 1.16

And now back to business, nothing really exciting yet: the next batch of exercises. The first is function up that in F# ends up being the same as concat, unless we define some new type.

// if not defining a new type that may be a list or a single element, 
// up will work like concat, on lists of lists
let rec up lst = 
    match lst with
      [] -> []
    | (l :: rlst) -> l @ (up rlst)

This is the Scheme version of up, for comparison:

(define up
  (lambda (lst)
    (if (null? lst)
      '()
      (if (list? (car lst)
        (append (car lst) (up (cdr lst)))
        (cons (car lst) (up (cdr lst)))))))

The next functions work on lists of symbols, so we repeat here the necessary type definition for symbol expressions.

type SymbolExp = Symbol of string | SList of SymbolExp list 

And the functions can thus be written:

let rec swapper s1 s2 slist = 
    match slist with
      [] -> []
    | (s :: rslist) -> swapper_in_symbol_exp s1 s2 s :: 
                      (swapper s1 s2 rslist)
and swapper_in_symbol_exp s1 s2 sexp = 
    match sexp with
      (Symbol s) when s = s1 -> Symbol s2
    | (Symbol s) when s = s2 -> Symbol s1
    | (SList sl) -> SList (swapper s1 s2 sl)
    | _ -> sexp

let rec count_occurrences sym slist = 
    match slist with
      [] -> 0
    | (s :: rsl) -> (count_occurrences_sexp sym s) + 
                    (count_occurrences sym rsl)
and count_occurrences_sexp sym sexp = 
    match sexp with
      (Symbol s) when s = sym -> 1
    | (SList sl) -> count_occurrences sym sl
    | _ -> 0
    
let rec flatten slist = 
    match slist with
      [] -> []
    | ((Symbol s) :: rsl) -> (Symbol s) :: (flatten rsl)
    | ((SList sl) :: rsl) -> (flatten sl) @ (flatten rsl)
    
// lon1 and lon2 are sorted lists of numbers
let rec merge lon1 lon2 = 
    match (lon1, lon2) with
      ([], _) -> lon2
    | (_, []) -> lon1
    | (x :: rlon1, y :: rlon2) when x <= y -> x :: (merge rlon1 lon2)
    | (x :: rlon1, y :: rlon2) -> y :: (merge lon1 rlon2)