Real World Haskell Chapter 5 – Scheme

For the chapter 5 JSON exercises I needed to update the prelude scheme library to add intercalate. I also wrote the following scheme files which are just ported versions of the haskell equivalents.

• prettify.ss
• simple-json.ss
• pretty-json.ss
• put-json.ss

Data types – JValue

The main headache attacking these exercises was the data type declarations. I took a very simple approach using PLT’s define-structure. This involved writing a whole lot of boilerplate code for contructors and type predicates. I think in the long run it would be a good idea to write some syntax extensions to deal with data declarations – something that allows you to write something like (data jvalue (jnumber number?) (jnull jnull?) ...) which generates the structure definition, constructors and type predicates for you. I’m too lazy to bother for now, but I’ll probably add it to the prelude later.

The first step was to define the jvalue types – as I said I used define-structure for jvalue type. The simple constructors for jstring, jnull, jbool and jnumber are not too interesting but jobject and jarray need a little extra effort. I thought about using an assoc list but I plumped for a hash-table as the underlying storage for jobjects. As scheme isn’t statically typed, the type predicate jarray ought to be defensive and check that it’s elements are all jvalue types. Luckily define-structure automatically generates type predicates which help, so internally a jarray is a simple list of jvalue elements.

(define-struct jvalue (type data))

(define (jtype-eq? value jtype) 
  (and (jvalue? value) 
       (eq? jtype (jvalue-type value))))

(define (jobject? value) 
  (and (jtype-eq? value 'jobject)
       (andmap (hash-map (λ (k v) 
                           (and (string? k) (jvalue? v)))
                         (jvalue-data value)))))

(define (jobject value) 
  (if (hash? value)
      (make-jvalue 'jobject value)
      (error "jobject expects type hash : " value)))

(define (jarray? x) 
  (and (jtype-eq? x 'jarray) 
       (andmap jvalue? (jvalue-data x))))

(define (jarray value) 
  (if (list? value)
      (make-jvalue 'jarray value)
      (error "jobject expects type array : " value)))

The Doc data type and values

I took an identical approach to creating the doc data type – with the added need to deconstruct Union and Concat values with simple accessor procedures.

(define (concat? value) (doc-type=? value 'concat))
(define (concat l r) (make-doc 'concat (cons l r)))
(define (concat-l c) (car (doc-data c)))
(define (concat-r c) (cdr (doc-data c)))

(define (union? value) (doc-type=? value 'union))
(define (union l r) (make-doc 'union (cons l r)))
(define (union-l c) (car (doc-data c)))
(define (union-r c) (cdr (doc-data c)))

There wasn’t much else of interest writing nest or fill in the general pretty-printing exercises – just a straightforward port of the haskell versions.

Pretty printing JSON unicode characters

The other points worth noting were dealing with the pretty-printing of json values. The full unicode spec is a bit over my head as are the various implementations and encodings – especially as the haskell functions introduce writing astral characters – I had to look those up.

The first thing I needed to do was to find the correct way of representing the various simple escape character literals. I couldn’t find them searching the PLT scheme documentation. Still it was easy enough for example to find the character using (string-ref “\f” 0) and so I eventually constructed an alist which I’m posting here for posterity and my own future reference.

(define simple-escapes 
  '((#\backspace . "\\b")
    (#\newline   . "\\n")
    (#\page      . "\\f")
    (#\return    . "\\r")
    (#\tab       . "\\t")
    (#\\         . "\\\\")
    (#\"         . "\\\"")
    (#\/         . "\\/")))

A couple of nice things I discovered were (at least in mzscheme) support for unicode hex literal characters and formatting #\uFF is the character literal for the ascii 255 character.

(format "~c" #\page)  => "\f"
(format "~c" #\uFF)   => "ÿ"
(format "~c" #\uFFFF) => "\uFFFF"

Unfortunately there seems to be disagreement about formatting astral characters – in PLT scheme they use the literal form of #\un where n looks to be a 64 bit value.
I’ve no idea why the haskell astral values are represented the way they are:

\uA a\uB : 
A = upper 10 bits + 0xd800
B = lower 10 bits + 0xdc00

Presumably it’s all there in the unicode spec. somewhere. So I decided to follow the haskell version but I’m not sure which is better or correct for JSON values. I guess it’s all there in the JSON spec too.

Real World Haskell Chapter 5 – Haskell

There are only 2 exercises in Chapter 5 which both live in the Prettify.hs file.
I’ve uploaded all of the files I created developing the JSON library for completeness and to be able to actually compile and use it.
Chapter 5 JSON library exercise solutions:

• Prettify.hs
• SimpleJSON.hs
• PrettyJSON.hs
• Main.hs
• PutJSON.hs

The files I wrote to create the libraries cabal package:

• Setup.hs
• pretty.cabal

All in all I found this chapter a bit confusing which I think is because the ideas behind it are obviously based on the built in Haskell pretty printing library which isn’t introduces until the end of the chapter. There was no real clear explanation of the structure and purpose of the different parts of the library which made reading and following some of the ideas very dry. Plus not much clarity about the placing of some of the definitions, stubs and functions.

Having said that the overall structure for writing the exercise solutions are given in the pretty and compact functions so both exercises were just a matter of adapting them to the job at hand.

Exercise 1

Keep a note of the current column (in the same way pretty does) and whenever a Line is encountered append spaces at the end of the current line to pad it out to the required width. The rest of the tree structure of the Document is maintained ‘as is’.

fill :: Int -> Doc -> Doc
fill width d = scanLines 0 [d]
    where scanLines col (d:ds) =
              case d of
                Empty        -> Empty  scanLines col ds
                Char c       -> d  scanLines (col + 1) ds
                Text s       -> d  scanLines (col + length s) ds
                Line         -> (padLine col  Line)  scanLines 0 ds
                a `Concat` b -> scanLines col (a:b:ds)
                a `Union` b  -> scanLines col (a:ds) `Union`  scanLines col (b:ds)
          scanLines _ _ = Empty
          padLine pos = text $ replicate (width - pos) ' '

Exercise 2

This works in the same way that fill does except the current line’s nesting position is maintained rather than the current item’s character position in the current line.
When an open brace or bracket is found the nesting is increased and when closing braces or brackets are found the nesting is decreased. After a new Line spaces are added to the beginning of the line according to the current nesting value. In the renderJValue function braces are implemented using only Char Doc values
- initially I also checked inside Text Doc values as well but realized that it isn’t necessary.

nest :: Int -> Doc -> Doc
nest indent d = scanLines 0 [d]
    where scanLines col (d:ds) =
              case d of
                Empty        -> d  scanLines col ds
                Char c       -> d  scanLines (col + offset c) ds
                Text s       -> d  scanLines col ds
                Line         -> d  indentLine col  scanLines col ds
                a `Concat` b -> scanLines col (a:b:ds)
                a `Union` b  -> scanLines col (a:ds) `Union`  scanLines col (b:ds)
          scanLines _ _        = Empty

          indentLine pos    = text $ replicate pos ' '
          offset c | c `elem` "{[" = indent
                   | c `elem` "}]" = negate indent
                   | otherwise     = 0

Chapter 5 – Ruby

Chapter 5 solutions

There are no list comprehensions in Ruby but most of the time blocks and Enumerable objects do the trick.
The trick being choosing whether to use map for unfiltered comprehensions, or inject, select, reject or something else for filtered comprehensions. Nested comprehensions could be a bit trickier though – I’ll wait and see if there are more complex nested examples later in the book.

A simple unfiltered comprehension just uses map

def double_all(xs)
  xs.map{ |x| 2 * x }
end

select can be used for inclusive filtered comprehensions with reject for exclusive filters.

def divisors(n)
  (1..n).select { |i| n % i == 0 }
end

Here though inject is needed rather than select because the object being yielded to the block is more complicated and thee whole thing isn’t being returned.
In a real life application though the objects being yielded into the block would probably have methods to return the desired results (the book in this case.)

def books(d_base, person)
  d_base.inject([]) { |loaned, loan| loan[0] == person ? loaned << loan[1] : loaned }
end

I think haskell wins at comprehensions though.

Chapter 5 – Scheme

Chapter 5 solutions.

The most interesting thing for me in this chapter was the fact that I haven’t used list comprehensions in scheme before so delving into SRFI 42 was interesting. Unfortunately that was the best documentation I could find so there was a fair bit of head scratching on my part before I managed to complete the exercises. Scheme comprehensions are eager, not lazy. The expression actually generates all the values at execution time rather than when the value(s) are needed – in contrast with haskell where laziness is one of the cornerstones of the language.

The main problem with SRFI 42 is the dazzling number of comprehension types and generators along with the terse documentation. It was nice to stumble across string-ec though – it’s a nice compact way of mapping over the characters in a string. It would have been nice to have the ordering of the terms the same as haskell – it doesn’t take long to get used to.

(define (capital-letters s)
  (string-ec (: c s)
             (if (char-alphabetic? c))
             (char-upcase c)))

The other thing worth mentioning is the lack of type checking in scheme now that types have been introduced – I added a minimal amount of type-checking in the library database prodcedures – haskell suddenly feels a lot safer.

Chapter 5 – Haskell

Chapter 5 solutions.

Nothing very exciting in this chaper except introducing list comprehensions, which are a joy to use.

divisors :: Int -> [Int]
divisors x 
    | x <= 0    = []
    | otherwise = [ d | d <- [1..x], x `mod` d == 0]

These small exercises are getting a bit tedious – especially as the author of the book seems obsessed with converting between lower and upper case characters. Three more exercises to eliminate them in this chapter!