The Haskell Road, 1.6 – 1.10

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
Posted in F# | Leave a comment

Buy Japanese stocks now?

This post is quite off topic but I wanted to respond to an investment idea sent by a relative.  The question was, given that a lot of Japanese stocks have taken big hits after the disasters in Japan, is now a good time to buy?

The short answer is no, not in my opinion for two reasons.  First, the declines so far have not been that large and two, the nuclear disaster has yet to be resolved and no one knows how bad it might get.

First, lets take a look at some representative declines.  These are 1 year charts.

Toyota, Sony, Honda, Canon, and Nippon T&T are not at their one year lows.  Mitsubishi and Nomura Holdings are at or near their one year lows, and only Panasonic has dropped below it briefly.  Given the severity of the ongoing disaster to date, these drops do not seem excessive to me.  The destruction in Japan, even if the nuclear plants were to be completely controlled today (which they are not), will severely impact that economy for years.  Some companies will benefit, such as construction companies, but others will be hurt by the power disruptions and damaged manufacturing and transportation capacity, e.g., Panasonic.

For comparison with a similar disaster in Japan, here’s a chart showing the Japanese stock market around the time of the Kobe earthquake in 1995:

You can read the post on seekingalpha about this here.  The main takeaway is that the stock market continued to decline for months after the earthquake before eventually recovering.

As to my second reason for not investing in Japan now, the nuclear problems continue.  It is hard for anyone to know how bad it really is, including the operator of the plant.  There have been articles describing how officials in the Unites States think the problems are worse than the Japanese are reporting.   What if things get worse?

All in all, my guess is the market is properly handicapping the negative impact of the disaster to date, and the non-zero probability that conditions could continue to deteriorate.  In my opinion, buying Japanese stocks at this point is equivalent to betting on the roulette wheel in Las Vegas.  I don’t have an edge there, and I don’t know anymore about the disaster in Japan than the market.

Posted in stocks | Tagged | Leave a comment

The Haskell Road, 1.1 – 1.5

So let’s jump right in and go through the examples and exercises from the first 5 sections of chapter 1 of  “The Haskell Road to Logic, Math and Programming”.   The Haskell code snippets from the book that I post will be enclosed in “(* *)” comments, followed by my implementation in F#.  F# functions will be preceded by the inferred type in “//” comments when not explicitly typed.

The first few examples from the book:


(*
divides :: Integer -> Integer -> Bool
divides d n = rem n d == 0
*)

// val divides : int -> int -> bool
let divides d n = (n % d) = 0

(*
ldf :: Integer -> Integer -> Integer
ldf k n | divides k n = k
        | k^2 >  n    = n
        | otherwise   = ldf (k+1) n
*)

// val ldf : int -> int -> int
let rec ldf k n =
   match k with
   | _ when divides k n -> k
   | _ when pown k 2 > n -> n
   | _ -> ldf (k+1) n

(*
ld :: Integer -> Integer
ld n = ldf 2 n
*)

// val ld : int -> int
let ld n = ldf 2 n

(*
prime0 :: Integer -> Bool
prime0 n | n < 1     = error "not a positive integer"  | n == 1    = False  | otherwise = ld n == n *) // val prime0 : int -> bool
let prime0 n =
   match n with
   | _ when n < 1  -> failwith "not a positive integer"
   | _ when n = 1  ->  false
   | _ -> ld n = n

(*
mnmInt :: [Int] -> Int
mnmInt [] = error "empty list"
mnmInt [x] = x
mnmInt (x:xs) = min x (mnmInt xs)
*)

// val mnmInt : 'a list -> 'a when 'a : comparison
let rec mnmInt l =
   match l with
   | [] -> failwith "emptylist"
   | [x] -> x
   | hd:: tail -> min hd (mnmInt tail)

(*
min' :: Int -> Int -> Int
min' x y | x <= y    = x            | otherwise = y *) // val min' : 'a -> 'a -> 'a when 'a : comparison
let min' x y =
   match x with
   | _ when x <= y -> x
   | _ -> y

A word on types. In the first few pages of the book, the authors jump between using type inference, Ints, and Integers. In the above F# code I’ve used int literals and otherwise relied on type inference.    If BigInts were instead desired to match the use of Haskell Integers in the book, explicit types could be specified and/or literals could be suffixed with “I”.

Exercise 1.9:

// val maxInt : 'a list -> 'a when 'a : comparison
let rec maxInt l =
   match l with
   | [] -> failwith "emptylist"
   | [x] -> x
   | hd:: tail -> max hd (maxInt tail)

Exercise 1.10

//val removeFst : 'a -> 'a list -> 'a list when 'a : equality
let rec removeFst m l =
   match l with
   | [] -> []
   | [x]  when x = m -> []
   | x::xs when x = m -> xs
   | x::xs -> x :: removeFst m xs

The next example, 1.11, is a little more interesting.  It is the first instance so far in the book where there is not a direct F# equivalent for some Haskell syntax.  Specifically, the srtInts function below uses a Haskell “where” clause within a pattern match.  There is nothing like it as far as I know in F#.    So I’ve used an F# active pattern instead:

(*
srtInts  ::  [Int]  ->  [Int]
srtInts  []  =  []
srtInts  xs  =  m  :  (srtInts  (removeFst  m  xs))  where  m  =  mnmInt  xs
*)

// val ( |XS| ) : 'a list -> 'a list * 'a when 'a : comparison
let (|XS|) xs = (xs, mnmInt xs)

// val srtInts : 'a list -> 'a list when 'a : comparison
let rec srtInts l =
   match l with
   | [] -> []
   | XS (xs,m) -> m:: srtInts (removeFst m xs)

A few more examples:

(*
average :: [Int] -> Rational
average [] = error "empty list"
average xs = toRational (sum xs) / toRational (length xs)
*)

// val average : int list -> float
let average l =
   match l with
   | [] -> failwith "empty list"
   | xs -> float (List.sum xs) / float (List.length xs)

(*
sum' :: [Int] -> Int
sum' [] = 0
sum' (x:xs) = x + sum' xs
*)

// val sum' : int list -> int
let rec sum' l =
   match l with
   | [] -> 0
   | x::xs -> x + sum' xs

(*
length' :: [a] -> Int
length' [] = 0
length' (x:xs) = 1 + length' xs
*)

// val length' : 'a list -> int
let rec length' l =
   match l with
   | [] -> 0
   | x::xs -> 1 + length' xs

Exercises 1.13, 1.14, and 1.15:

Here we encounter our next difference between Haskell and F#.  In Haskell, String is simply an abbreviation  for a list of Chars.  This is not the case in F#.  Since it seems that up to this point the intent of the exercises is to process lists recursively, I’ve decided to implement the exercises using F# char lists instead of F# strings.


(* Exercise 1.13 *)
// val count : char -> char list -> int
let rec count (c: char) (l : char list) =
   match l with
   | [] -> 0
   | x::xs when x = c -> 1 + count c xs
   | _::xs -> count c xs

(* Exercise 1.14 *)
let blowup (s: char list) : char list =
   let rec repeat (chr:char) (cnt:int)  =
       [ if ( cnt > 0 ) then
            let cnt = cnt - 1
            yield chr
            yield! repeat chr cnt ]
   let rec xblowup (s: char list) (index: int) : char list =
       match s with
       | [] -> []
       | x::xs -> [yield! repeat x index
                   yield! xblowup xs (index + 1) ]

   xblowup s 1

(* Exercise 1.15 *)

// val minStr : char list -> char list -> char list
let minStr (s1:char list) (s2: char list) =
   let rec rminStr (rs1:char list) (rs2: char list) =
      match rs1,rs2 with
      | [],_ -> s1
      | _,[] -> s2
      | x::xs,y::ys when x < y -> s1
      | x::xs,y::ys when y < x -> s2
      | x::xs,y::ys -> rminStr xs ys
   rminStr s1 s2

// val mnmStr : char list list -> char list
let rec mnmStr (l:char list list) =
   match l with
   | [] -> failwith "emptylist"
   | [x] -> x
   | hd:: tail -> minStr hd (mnmStr tail)

// val ( |SXS| ) : char list list -> char list list * char list
let (|SXS|) (xs :char list list) = (xs, mnmStr xs)

// val srtStrs : char list list -> char list list
// val srtStrs : char list list -> char list list
let rec srtStrs (l: char list list) : char list list =
   match l with
   | [] -> []
   | SXS (xs,m) -> m:: srtStrs (removeFst m xs)

And finally, example 1.16

(*
prefix :: String -> String -> Bool
prefix [] ys = True
prefix (x:xs) [] = False
prefix (x:xs) (y:ys) = (x==y) && prefix xs ys
*)
// val prefix : char list -> char list -> bool
let rec prefix (l1:char list) (l2:char list) : bool =
    match l1,l2 with
    | [], _ -> true
    | x::xs,[] -> false
    | x::xs,y::ys -> (x=y) && prefix xs ys

In my next blog post we’ll finish the chapter and encounter the biggest difference yet between Haskell and F# – Haskell’s infinite vs. F#’s finite lists.

Posted in F# | Leave a comment

Motivation

After years of object oriented development using Java, I thought it would be interesting to learn a functional language given the recent interest in Scala and F#. The purpose of this first post is not to debate the merits of the various functional languages but rather to motivate subsequent posts that I plan to make. Nevertheless I should say a few words about why this blog will be focused on Haskell and F#.

I’m biased towards strongly typed languages so once headed down the functional path I found that in addition to Scala and F# I should also consider Haskell. Scala is interesting because of the strong affinity with Java and its multi-paradigm nature. F# has strong tool support with Visual Studio 2010 and Microsoft’s backing which should enhance its popularity, and it is also multi-paradigm with its .Net integration. And of course Haskell is the most pure functionally.

I’ve spent some amount of time reading most of Martin Odersky’s excellent book “Programming in Scala”. Though I really wanted to like Scala, I’ve been frustrated by the language complexity, the poor though improving tool support, and its features that allow code to be written that cannot be readily deciphered by someone else. Jonathan Edwards has an excellent writeup on this so I won’t belabor the point.

Given the choice between F# and Haskell, I would prefer to invest in learning F# for the following reasons:

  1. the .Net platform is much richer than the Haskell Platform
  2. F# has better IDE support
  3. F#’s imperative and object oriented nature gives you a way out if you find you just can’t (or can’t easily) implement something using functional mechanisms.

But it seems that many of the most interesting books on functional programming use Haskell! In fact, one of my favorites so far, “The Haskell Road to Logic, Maths and Programming” by Kees Doets and Jan van Eijck uses Haskell. So as confusing as it is for me, I’m reading this book and doing the exercises in F#

In this blog I plan to post translations of the Haskell code in the book and the exercises I do in F#.

Posted in Uncategorized | Leave a comment