Inside F#

Brian's thoughts on F# and .NET

Pretty strings, and another scripting games problem

Posted by Brian on March 8, 2008

A mildly useful library is one that allows us to easily create "pretty" grids of text that display well on fixed-width-text consoles.  A very simple version of such a library is easy to describe: Imagine a new data type called "PrettyString" that represents a "box" of text.  There are two main operators on PrettyStrings: "++" for horizontal concatenation, and "%%" for vertical concatenation.  The function "pretty" takes in a string and returns a PrettyString object.  Here’s a short demo of such a library:

let blank = pretty " "
let str1 = (pretty "hey") %% (pretty "you") %% (pretty "there")
let str2 = pretty "check this out"
let row = str1 ++ blank ++ str2 ++ blank ++ str1
let rows = row %% row
printf "%s" (rows.ToString())

and here is the output:

hey   check this out hey
you                  you
there                there
hey   check this out hey
you                  you
there                there

Get the idea?  Using a few horizontal and vertical concatenations, it is pretty easy to lay out text into interesting grid formations.

There are many possible strategies for implementing the PrettyString type.  One of the most straightforward implementations is realized by a class hierarchy, where the concatenation operators just create an object graph that mimics the grid structure being laid out by the user.  Here is code that uses that implementation strategy:

open System
open System.Text
open Microsoft.FSharp.Collections

/// PrettyStrings are strings that support vertical and horizontal concatenation
/// for creating grids of text.
[<AbstractClass>]

type PrettyString() = 
    /// The number of lines in this PrettyString
    abstract Height : int
    /// The width of this PrettyString (width of the longest line)
    abstract Width : int
    /// Get the nth line.  If n is not in the range [0..Height), then return the empty string.
    abstract Line : int -> string
    override this.ToString()
        let sb = new StringBuilder()
        for i in 0 .. this.Height do
            sb.Append(this.Line i) |> ignore
            sb.Append("\n") |> ignore
        sb.ToString()

type StringLiteral(s:string) =
    inherit PrettyString()
    // TODO: if the input string contains newline characters, 
    // things will be ugly.  Ignoring that issue for now.
    override this.Height = 1
    override this.Width = s.Length
    override this.Line n = if n <> 0 then "" else s
    
type Vertical(top:PrettyString, bottom:PrettyString) =
    inherit PrettyString() 
    override this.Height = top.Height + bottom.Height
    override this.Width = Math.Max(top.Width, bottom.Width)
    override this.Line n =
        if n < 0 || n >= this.Height 
        then ""
        else if n < top.Height
             then top.Line n
             else bottom.Line (n – top.Height)

type Horizontal(left:PrettyString, right:PrettyString) =
    inherit PrettyString()
    override this.Height = Math.Max(left.Height, right.Height)
    override this.Width = left.Width + right.Width
    override this.Line n =
        String.Concat(left.Line(n).PadRight(left.Width)
                      right.Line(n))

let pretty s = new StringLiteral(s) :> PrettyString

let (%%) x y = new Vertical(x,y) :> PrettyString
let (++) x y = new Horizontal(x,y) :> PrettyString

PrettyString is an abstract class that knows its width and height, and can return its nth line of text, or the whole text string (containing newlines).  There are three concrete subclasses (StringLiteral, Vertical, Horizontal) which correspond to the three main functions of the library API (pretty, %%, ++). 

The implementation is straightforward.  For those readers unfamiliar with F#, here is a brief synopsis of some syntax.  The "type" keyword introduces new types; in the code above, F# infers from the members in the body of the types that these types are classes.  "inherit" defines a subclass relationship.  You can explicitly specify the type of an entity with the syntax "name:type", though thanks to type inference you rarely need to write explicit type annotations. The keywords "abstract" and "override" mean the same as in C#.  (Though there are no examples here of it, if we wanted to declare a normal non-virtual method, we would use the "member" keyword.)  The parenthesized arguments after the type name in the type declaration are used to declare a constructor for the class; these arguments can be treated liike fields in the class.  ":>" is the upcast operator, used, for example, so that "pretty s" has type PrettyString rather than type StringLiteral.  F# allows you to define new infix operators, as we did with "%%" and "++" here.  Take a moment to read over the code and understand it.

With this code in hand, we are well-poised to code up a solution to another problem from the 2008 Winter Scripting GamesThis problem asks us to pretty print a calendar for a given month and year.  So let’s say our goal is to write a "calendar" function such that

let Feb2008 = calendar 2008 2
printf "%s" (Feb2008.ToString())

yields output like

February 2008
Su Mo Tu We Th Fr Sa
                1  2
 3  4  5  6  7  8  9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29

Here’s the code:

let calendar year month =
    let maxDays = DateTime.DaysInMonth(year, month)
    // make the column that starts with day i (e.g. 1, 8, 15, 22, 29)
    let makeColumn i =
        let prettyNum (i:int) = pretty(i.ToString().PadLeft(2))
        let mutable r = prettyNum i
        let mutable j = i + 7
        while j <= maxDays do
            r <- r %% prettyNum j
            j <- j + 7
        r
        
    let firstOfMonth = new DateTime(year, month, 1)
    let firstDayOfWeek = int firstOfMonth.DayOfWeek
    // create all the columns for this month’s calendar, with Sundays in columns[0]
    let columns = Array.create 7 blank
    for i in 0 .. 6 do
        columns.[(i + firstDayOfWeek) % 7] <- makeColumn (i+1)
    // if, for example, the first of the month is a Tuesday, then we need Sunday and Monday
    // to have a blank in the first row of the calendar   
    if firstDayOfWeek <> 0 then
        for i in 0 .. firstDayOfWeek-1 do
            columns.[i] <- blank %% columns.[i]
    // put the weekday headers at the top of each column
    let dayAbbrs = [| "Su"; "Mo"; "Tu"; "We"; "Th"; "Fr"; "Sa" |]
    for i in 0 .. 6 do
        columns.[i] <- pretty(dayAbbrs.[i]) %% columns.[i]
    // Horizontally concatenate all of the columns together, with blank space between columns
    let calendarBody = Array.reduceBack (fun x y -> x ++ blank ++ y) columns
    // Surely there must be a .NET call that turns a month number into its name,
    // but I couldn’t find it when I was typing this up. 
    let monthNames = [| "January" ; "February"; "March"; "April"; "May"; "June"
        "July"; "August"; "September"; "October"; "November"; "December" |]
    let titleBar = pretty(sprintf "%s %d" monthNames.[month-1] year) 
    titleBar %% calendarBody

Again, for those unfamiliar with F#, here are a few more notes on syntax.  "let" is used to define both values and functions.  "mutable" is used for defining mutable variables, which can later be re-assigned new values using the assignment operator "<-".  Array literals appear in [| these brackets |], and arrays are indexed like.[this].  Functions can be defined to take arguments either as tuples or in curried form.  Outside of F#, .NET functions take tuples, so for example we call DaysInMonth with the arguments inside parentheses and separated by commas:

    DateTime.DaysInMonth(year, month)

whereas typically functions you write in F# use the curried form, so for example calling this F# library function (that creates a fresh array with a given default value in each cell) looks like this:

    Array.create 7 blank

where the arguments are not contained in parentheses or separated by commas. 

One common idiom in functional programming is using a "fold" (sometimes called a "reduce") to apply a function to a given data structure to accumulate a final value. The call to Array.reduceBack is an example of this.  The syntax "fun args -> body" defines a new anonymous function (lambda).  In the calendar function, this expression

  Array.reduceBack (fun x y -> x ++ blank ++ y) columns

is a way to compute

   columns.[0] ++ (… ++ (columns.[5] ++ columns.[6])…)

Have a look at the definition of "reduceBack" in the library docs if you have not encountered such "fold"s before.

Though you could write the "calendar" function without using PrettyString, our little library makes it easy to make the rows and columns line up just so.  In fact, I have been sitting on the PrettyString code for a couple weeks, and then recently I discovered this calendar problem and realized it makes for a great excuse to post a blog entry about PrettyString.  Furthermore, I am glad to have written my first F# blog post that shows code with classes and class hierarchies.  Many F# blogs just illustrate the functional core of the language, and I want to provide some balance by showing code with classes, arrays, mutable variables, and the many other features that make F# effective as a general purpose programming language.

Advertisements

One Response to “Pretty strings, and another scripting games problem”

  1. Scott said

    Brian,
    Can you put up something showing how to use attributes in F#? I\’d especially like to see a datatype set up to use DataContract combined with F#. It\’s just another area that the F# blogs are skipping.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: