Before I could tackle the exercises in chapter 4 I think it would be useful to have some of the nice functions from Haskell’s prelude, so I wrote a prelude library to help. I’ll be updating it as I work my way through the book.
Scheme prelude and the lazy version
Interact with text file framework
First words program
Transpose text program
Chapter 4 exercise solutions
The start of chapter 4 gives a framework for transforming text files which I needed to convert into Scheme.
The only complex part is being able to invoke a scheme text file as a script, but the PLT documentation gives the answer. I’m not sure how this would work under windows, but there must be an equivalent. I’m posting the magic part here for posterity and so I can find it more easily in the future.
Their script uses exec mzscheme -cu "$0" ${1+"$@"}.
The -c switch disables loading compiled files (which I think causes some/a;; of the library functions used to be loaded and compiled when the script runs but I got tired of the extra delay caused so I’m using:
#! /bin/sh
#|
exec mzscheme -u "$0" ${1+"$@"}
|#
#lang scheme/base
I realise I have no idea how the Haskell code schedules and performs the reading and writing of the files.
I began to wonder about efficiency though or more precisely the lazy nature of Haskell and how reading in a text file line by line and processing it actually works. According to the documentation readFile the file is read in lazily line by line as required so I expect it depends on how function uses the list of strings it is passed.
interactWith function inputFile outputFile = do input <- readFile inputFile writeFile outputFile (function input)
I tried 2 different approaches in Scheme:
- Reading in the whole file into a list of strings, then performing the transformation on each line in the list.
- Reading and writing the file a line at a time, performing the transformation and writing it as it is read.
I went with the second option initially and so the framework code for transforming a file:
(define (main)
(define arguments (current-command-line-arguments))
(if (= (vector-length arguments) 2)
(let ([in (vector-ref arguments 0)]
[out (vector-ref arguments 1)])
(interact-with my-function in out))
(error "interact-with expects exactly 2 arguments : interact-with in-file-path out-file-path\n\tProvided : " arguments)))
The procedure that applies the line by line transformation
(define (interact-with f in out)
(with-output-to-file out #:mode 'text #:exists 'replace
(λ ()
(with-input-from-file in
(λ ()
(let next-line ([line (read-line)])
(cond [(eof-object? line) (void)]
[else (write-string (f line))
(newline)
(next-line (read-line))])))
#:mode 'text))))
I thought of using call-with-input-file and call-with-input-file but I couldn’t find a neat way of capturing the procedure to transform each line without writing a nested procedure, but it doesn’t seem any more elegant.
I didn’t convert the FixLines to Scheme as mzscheme seems to cope with both Unix and Windows line separators (at least in the Ubuntu version.)
Exercise 1
I can see I’m going to get in a lot of trouble later on in the book coping with Haskell’s type system under Scheme but here goes with Maybe. I think there must be a way of using macros to cope with types like Maybe, but I’ll leave that as an exercise for myself. I have enough new concepts in Haskell to take on-board currently.
(define-struct maybe (value)) (define Just make-maybe) (define Nothing (make-maybe 'Nothing)) (define (nothing? o) (equal? o Nothing)) (define (safe-head o) (if (null? o) Nothing (Just (first o)))) (define (safe-tail o) (if (null? o) Nothing (Just (rest o)))) (define (safe-last o) (if (null? o) Nothing (Just (last o)))) (define (safe-init o) (if (null? o) Nothing (Just (init o))))
The init and last procedures are in the Scheme Prelude library I wrote.
Exercise 2
I’m using values and let-values to implement an analogue of tuples for example in defining and using span and break but I ran into a problem with that which I’ll explain later. The split-with that preserves all list members:
(define (split-with+ p xs)
(cond [(null? xs) null]
[else (let-values ([(head) (first xs)]
[(pre suf) (span p (rest xs))])
(cons (cons head pre)
(split-with+ p suf)))]))
The non-preserving version:
(define (split-with p xs)
(define (split-suffix suf) (split-with p (drop-while (combine not p) suf)))
(if (null? xs)
null
(let-values ([(pre suf) (span p xs)])
(if (null? pre)
(split-suffix suf)
(cons pre (split-suffix suf))))))
Exercise 3
Once again it’s a little messier dealing with strings – using a higher order functional approach to deal with strings requires converting strings into lists of characters and back again. Still at least Scheme has procedures for that.
(define char-nonspace? (compose not char-whitespace?))
(define (first-word line)
(list->string
(take-while char-nonspace?
(drop-while char-whitespace? (string->list line)))))
Exercise 4
The transpose procedure needs all the lines of text before it can work and so I had to switch back to my first approach for dealing with text files, namely to read the whole file into a list of strings, then apply the transformation, then write out the result.
(define (interact-with f in out) (write-lines out (f (read-lines in))))
(define (read-lines in)
(with-input-from-file in
(λ ()
(let next-line ([line (read-line)])
(if (eof-object? line)
null
(cons line (next-line (read-line))))))
#:mode 'text))
(define (write-lines out ls)
(with-output-to-file out #:mode 'text #:exists 'replace
(λ () (for-each (λ (line) (write-string line) (newline)) ls))))
Picking the first letter of each line and and the rest of the letters from each line is a little more fiddly in Scheme but for the Haskell version I also had to write extra functions to mimic head and tail to be able to use map safely on different length lines.
I’m still not entirely happy that it doesn’t pad spaces in front of transposed lines as you’d expect but it works for lines of the same length and so that’s goods enough for now.
(define (transpose-lines lines)
(let ([heads (apply string-append (map safe-string-first lines))]
[tails (map safe-string-rest lines)])
(if (string-empty? heads)
null
(cons heads (transpose-lines tails)))))
(define empty-string "")
(define (string-empty? s) (string=? s empty-string))
(define (safe-string-first s) (if (string-empty? s) empty-string (substring s 0 1)))
(define (safe-string-rest s) (if (string-empty? s) empty-string (substring s 1)))
Folds Exercise 1
Basically the same as the Haskell version except for once again using string based functions instead of list based ones.
(define (as-int-fold ds)
(cond [(string=? ds "") 0]
[(char=? (string-ref ds 0) #\-) (- (as-int-fold (substring ds 1)))]
[else (foldl shift-right-and-add
0
(string->list ds))]))
(define (shift-right-and-add d acc)
(+ (* 10 acc)
(char->digit d)))
Then for fun I decided to try using a right fold but I ran into a problem. Let’s say our string has 4 digits d1 d2 d3 d4 and the intermediate result after processing d4 and d3 is res so d1 * 1000 + (d2 * 100 + (d3 * 10 + (d4 * 1)))
At each iteration 3 values are needed – the current result, the current digit and the factor needs to be multiplied by 10 to give
So I wrote:
(define (shift-right-and-add+ d acc)
(let-values ([(res factor) acc])
(+ (* 10 acc)
(char->digit d)))
But calling it with (foldr shift-right-and-add+ (values 0 1) (string->list ds)) -> error: context expected 1 value, received 2 values: 0 1
Considering I’d finished the exercise with a left fold I checked out the comments for the exercise on the Real World Haskell web site and found the delightful:
asInt_fold:: String -> Int
asInt_fold ('-':rest) = -asInt_fold (filter isDigit rest)
asInt_fold str = foldr step 0 (reverse str)
where step i acc = acc * 10 + digitToInt i
I really wish I’d had the insight to think of that. Thank you Marcus Edwards.
This means the same step function can be used as with the left fold version and gives the much more elegant:
(define (as-int-foldr ds)
(cond [(string=? ds "") 0]
[(char=? (string-ref ds 0) #\-) (- (as-int-foldr (substring ds 1)))]
[else (foldr shift-right-and-add
0
(reverse (string->list ds)))]))
I won’t comment on the other solutions as they are pretty much just conversion from Haskell into the appropriate Scheme.
Except for the cycle exercise. The only way I could think of doing this in Scheme is to use delay, force and promise but that would mean re-writing all list handling functions but luckily PLT has a lazy scheme language which can be used almost interchangeably with regular scheme. I’m considering using this for future exercises, but for now this is a stand-alone exercise using the PLT lazy scheme language.
#lang lazy (define (integers-from n) (cons n (integers-from (add1 n)))) (define (ba-cycle xs) (define (cycle-step x acc) (cons xs acc)) (foldr cycle-step null (integers-from 0)))
