Continuing the exercises in chapter 1 of “The Haskell Road to Logic, Math and Programming” from where I left off last time:
Exercises 1.17, 1.20, and 1.21
(* Exercise 1.17 *)
let rec substring (l1:char list) (l2:char list) : bool =
match l1,l2 with
| xs, ys when prefix xs ys -> true
| xs , y::ys -> substring xs ys
| _ , _ -> false
(* Exercise 1.20 *)
let lengths l =
List.map length' l
(* Exercise 1.21 *)
let sumLengths l =
let listofLens = lengths l
sum' listofLens
Section 1.7:
(*
factors :: Integer -> [Integer]
factors n | n < 1 = error "argument not positive"
| n == 1 = []
| otherwise = p : factors (div n p) where p = ld n
*)
let (|P|) (n:int) = (n, ld n)
let rec factors n =
match n with
| _ when n < 1 -> failwith "argument not positive"
| x when x = 1 -> []
| P (n, p') -> p' :: factors ( n / p')
Example 1.22
Here is the biggest difference between Haskell and F# that we’ve encountered so far. The book uses the Haskell infinite list [2 . .] to generate an infinite list of prime numbers. In F#, lists are finite so we could define a finite list of primes like this:
let primes0x = List.filter prime0 [2I .. int System.Int32.MaxValue ]
The entire list would be created at once in memory which would be quite wasteful in terms of memory and CPU if the entire list was not really needed. Instead, let’s try using F# sequences, which are evaluated lazily and can be infinite. We could define an infinite sequence of ints like this:
let allInts =
let rec loop x = seq { yield x; yield! loop (x + 1 ) }
loop 0
But let’s use the F# built-in function and define an infinite sequence of primes like this
let primes0 = Seq.filter prime0 (Seq.initInfinite(fun i -> i+2 ))
Example 1.23
Using the approach above for generating an infinite sequence of primes:
(*
ldp :: Integer -> Integer
ldp n = ldpf primes1 n
ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n | rem n p == 0 = p
| p^2 > n = n
| otherwise = ldpf ps n
primes1 :: [Integer]
primes1 = 2 : filter prime [3..]
prime :: Integer -> Bool
prime n | n < 1 = error "not a positive integer"
| n == 1 = False
| otherwise = ldp n == n
*)
let (|SPLIT|) (xs: int seq) = (Seq.head xs, Seq.skip 1 xs)
//ldp :: Integer -> Integer
let rec ldp n = ldpf primes1 n
// ldpf :: [Integer] -> Integer -> Integer
and ldpf (p:int seq) (n:int) =
match p with
| SPLIT (p,ps) when divides p n -> p
| SPLIT (p,ps) when (pown p 2) > n -> n
| SPLIT (p,ps) -> ldpf ps n
// primes1 :: [Integer]
and primes1 = Seq.append (seq {yield 2}) (Seq.filter prime (Seq.initInfinite(fun i -> i+3)))
// prime :: Integer -> Bool
and prime n =
match n with
| _ when n < 1 -> failwith "not a positive integer"
| _ when n = 1 -> false
| _ -> (ldp n) = n
The problem here is that from what I’ve read any “time you break apart a seq using “Seq.hd” and “Seq.skip 1″ you are almost surely falling into the trap of going O(N^2).” So much for that approach. It turns out that the F# PowerPack provides a lazy list implementation. Now we can write:
//ldp :: Integer -> Integer
let rec ldp n = ldpf primes1 n
// ldpf :: [Integer] -> Integer -> Integer
and ldpf (pr:int LazyList) (n:int) =
match pr with
| LazyList.Cons(p,ps) when divides p n -> p
| LazyList.Cons(p,ps) when (pown p 2) > n -> n
| LazyList.Cons(p,ps) -> ldpf ps n
| LazyList.Nil -> failwith "only call w/ an infinite list"
// primes1 :: [Integer]
and primes1 = LazyList.unfold (fun p -> Some(p, p+1)) 2
// prime :: Integer -> Bool
and prime n =
match n with
| _ when n < 1 -> failwith "not a positive integer"
| _ when n = 1 -> false
| _ -> (ldp n) = n
