Climbing the Towers of Hanoi with Haskell-style Curry from a Monadic Container (While Sparing the Sugar!)

Have you ever felt like eating some Haskellian curry on your way to the top of the Towers of Hanoi, but could do without the sugar in the container? Well, here’s how….

Previously, I had posted the following solution to the Towers of Hano problem:

hanoi :: a -> a -> a -> Int -> [(a, a)]
hanoi source using dest n
    | n == 0 = []
    | n == 1 = [(source, dest)]
    | otherwise = hanoi source dest using (n-1)
                  ++ hanoi source using dest 1
                         ++ hanoi using source dest (n-1)

hanoi_shower :: Show a => [(a, a)] -> String
hanoi_shower [] = ""
hanoi_shower ((a, b):moves) = unlines ["Move " ++ show a ++ " to "++ show b ++ "."] ++ hanoi_shower moves

However, this function seemed somewhat difficult to understand at a glance, and had the problem that it needed to be called as follows:

putStr (hanoi_shower (hanoi 'a' 'b' 'c' 3))

Thereupon, the function would reward the user with the following results:

Move 'a' to 'c'.
Move 'a' to 'b'.
Move 'c' to 'b'.
Move 'a' to 'c'.
Move 'b' to 'a'.
Move 'b' to 'c'.
Move 'a' to 'c'.

While technically a solution, this function had never seemed an entirely satisfactory counterpart to my earlier Scheme solution (part of the text in the output statement thereof below has been slightly reworded from “… from disc” to “… disc from” here for readability) to the same problem:

(define (hanoi n)
  (hanoi-helper 'A 'B 'C n))

(define (hanoi-helper source using destination n)
  (cond ((= n 1)
         (printf "Moving disc from ~a to ~a.\n" source destination))
        (else
         (hanoi-helper source destination using (- n 1))
         (hanoi-helper source using destination 1)
         (hanoi-helper using source destination (- n 1)))))

In particular, the Scheme version could be invoked quite simply as follows:

(hanoi 3)

Thereupon, it would reward the user with the following results:

Moving disc from A to C.
Moving disc from A to B.
Moving disc from C to B.
Moving disc from A to C.
Moving disc from B to A.
Moving disc from B to C.
Moving disc from A to C.

Why not the Haskell version?

At first, not understanding how to use monads correctly, I tried to write the following (incorrect) version, thinking that I could just concatenate the results of the recursive calls into one long string:

hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C"

hanoiHelper :: Integer -> String -> String -> String -> IO ()
hanoiHelper n source dest using
                | n == 1 = putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
                | otherwise = hanoiHelper (n-1) source using dest
                              ++ hanoiHelper 1 source dest using
                              ++ hanoiHelper (n-1) using dest source

However, attempting to load this function into WinGhci resulted in the following error message:

    Couldn't match expected type `[a]' against inferred type `IO ()'
    In the first argument of `(++)', namely
        `hanoiHelper (n - 1) source using dest'
    In the expression:
          hanoiHelper (n - 1) source using dest
        ++  hanoiHelper 1 source dest using
          ++
            hanoiHelper (n - 1) using dest source
    In the definition of `hanoiHelper':
        hanoiHelper n source dest using
                      | n == 1
                      = putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
                      | otherwise
                      = hanoiHelper (n - 1) source using dest
                      ++  hanoiHelper 1 source dest using
                        ++
                          hanoiHelper (n - 1) using dest source

Since the error message reported that the expected type of hanoiHelper was `[a]‘, I then tried modifying the type signature for hanoiHelper accordingly, as follows:

hanoiHelper :: Integer -> String -> String -> String -> [a]

Unfortunately, this only reported in the converse error, thus:

[1 of 1] Compiling Main             ( hanoiIncorrect.hs, interpreted )

hanoiIncorrect.hs:9:10:
    Couldn't match expected type `IO ()' against inferred type `[a]'
    In the expression: hanoiHelper n "A" "B" "C"
    In the definition of `hanoi': hanoi n = hanoiHelper n "A" "B" "C"

hanoiIncorrect.hs:13:27:
    Couldn't match expected type `[a]' against inferred type `IO ()'
    In the expression:
        putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
    In the definition of `hanoiHelper':
        hanoiHelper n source dest using
                      | n == 1
                      = putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
                      | otherwise
                      = hanoiHelper (n - 1) source using dest
                      ++  hanoiHelper 1 source dest using
                        ++
                          hanoiHelper (n - 1) using dest source
Failed, modules loaded: none.

Stumped, I came across the following example of code for solving this problem:

 hanoiM :: Integer -> IO ()
 hanoiM n = hanoiM' n 1 2 3 where
   hanoiM' 0 a b c = return ()
   hanoiM' n a b c = do
     hanoiM' (n-1) a c b
     putStrLn $ "Move " ++ show a ++ " to " ++ show b
     hanoiM' (n-1) c b a

However, I wasn’t satisfied with this solution, because the syntactic sugar of the do-notation obscured the semantics of what was happening. I liked to have my Haskell curry without sugar.

Then I came across the following explanation of an unsugared monad:

Let’s examine how to desugar a ‘do’ with multiple statements in the following example:

main = do putStr "What is your name?"
          putStr "How old are you?"
          putStr "Nice day!"

The ‘do’ statement here just joins several IO actions that should be performed sequentially. It’s translated to sequential applications of one of the so-called “binding operators”, namely ‘>>’:

main = (putStr "What is your name?")
       >> ( (putStr "How old are you?")
            >> (putStr "Nice day!")
          )

After comparing the two examples and looking at the nesting of parentheses for a while, I suddenly realized that monads must be some kind of container. Apparently, the monads served to contain something inside that was undesirable in a purely functional environment outside, and the bind (”>>”) notation could be nested to enforce sequencing on the execution order.

After some thought, I came up with the corresponding Haskell solution; viz.:

hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C" where
    hanoiHelper 1 source dest using = putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
    hanoiHelper n source dest using = (hanoiHelper (n-1) source using dest)
                                      >> ( (hanoiHelper 1 source dest using)
                                           >> (hanoiHelper (n-1) using dest source)
                                         )

This function type-checked correctly, and could be summoned as follows:

hanoi 3

Thereupon, similarly to its Scheme counterpart, it would now reward the user as follows:

Move disc from A to B.
Move disc from A to C.
Move disc from B to C.
Move disc from A to B.
Move disc from C to A.
Move disc from C to B.
Move disc from A to B.

For those who prefer do-notation, here is the same function sweetened with syntactic sugar:

hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C" where
    hanoiHelper 1 source dest using = putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
    hanoiHelper n source dest using = do
                                      hanoiHelper (n-1) source using dest
                                      hanoiHelper 1 source dest using
                                      hanoiHelper (n-1) using dest source

Although almost a direct counterpart to the corresponding Scheme version, it was still not structured similarly as a main function and a helper function; I wanted to divide it correspondingly.

Eventually, I came up with the following corresponding solution, which also used a helper function:

hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C"

hanoiHelper :: Integer -> String -> String -> String -> IO ()
hanoiHelper n source dest using
                | n == 1 = putStrLn ("Move disc from " ++ source ++ " to " ++ dest ++ ".")
                | otherwise = (hanoiHelper (n-1) source using dest)
                                      >> ( (hanoiHelper 1 source dest using)
                                           >> (hanoiHelper (n-1) using dest source)
                                         )

As a bonus, during my research, I chanced upon the following explanation of the ‘$’ operator:

$ operator

This is hopefully something worth sharing about Haskell. The $ operator.

 simpleHTTP $ buildRequest req_text

 simpleHTTP ( buildRequest req_text )

It is an application operator, it takes a function and an argument, and … applies the function to the argument. It’s purpose is to save typing parentheses. It is all about operator precedence.

 head . words $ config_file_contents

 ( head . words ) config_file_contents

Application, f a (f applies to a), binds stronger than any operator. If it was an operator, think about multiplication operator which people often omit, it would have precedence set to 10. $ has precedence set to 0, which is the lowest value of precedence possible.

The . is my another favourite. (f . g) a == f (g a) it set to 9, and therefore binds almost as strong as application.

 listActions :: String -> [Action]
 listActions = filter notDone . map actionFromMap . parseJSON

Feeling richer with the ‘$’, I rewrote my function, listed below complete with comments and a copyleft disclaimer, to suit my mood accordingly:

-- hanoiHelpedRich.hs
-- Haskell function to compute the Towers of Hanoi problem recursively, 
-- using a helper function and the '$' operator to take a function and 
-- an argument, and accordingly save typing parentheses
--
-- Copyright(C) April 13, 2009, at 19:56, 
-- by Benjamin L. Russell
-- 
-- This program is free software; you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation; either version 2 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
--
-- You should have received a copy of the GNU General Public License
-- along with this program; if not, write to the Free Software
-- Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C"

hanoiHelper :: Integer -> String -> String -> String -> IO ()
hanoiHelper n source dest using
                | n == 1 = putStrLn $ "Move disc from " ++ source ++ " to " ++ dest ++ "."
                | otherwise = (hanoiHelper (n-1) source using dest)
                                      >> ( (hanoiHelper 1 source dest using)
                                           >> (hanoiHelper (n-1) using dest source)
                                         )

Now I am on a diet with fewer parentheses, but with more ‘$’ in my pocket.

P.S.

One commentator, augustss, has been kind enough to point out that my version of hanoi can be rewritten to be less IO-based, and more functional. Per augustss’s suggestion, I have rewritten hanoi.hs as follows:

-- hanoiMover.hs
-- Originally based on hanoi_v1.1.hs, a Haskell function to compute
-- the Towers of Hanoi problem recursively, by Benjamin L. Russell,
-- dated April 16, 2008, at 14:17; 
-- revised based on a comment from augustss, dated April 18, 2009, at
-- 17:38, (see
-- http://dekudekuplex.wordpress.ecom/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/#comment-58),
-- in response to my blog post "Climbing the Towers of Hanoi with
-- Haskell-style Curry from a Monadic Container (While Sparing the 
-- Sugar!)," dated April 13, 2009, at 19:59 (see
-- http://dekudekuplex.wordpress.com/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/)
--
-- Copyright(C) April 20, 2009, at 18:38, 
-- by Benjamin L. Russell
-- 
-- This program is free software; you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation; either version 2 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
--
-- You should have received a copy of the GNU General Public License
-- along with this program; if not, write to the Free Software
-- Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

hanoi :: Integer -> IO ()
hanoi = putStr . hanoiShower . hanoiMover 'a' 'b' 'c'

hanoiMover :: a -> a -> a -> Integer -> [(a, a)]
hanoiMover source using dest n
    | n == 0 = []
    | n == 1 = [(source, dest)]
    | otherwise = hanoiMover source dest using (n-1)
                  ++ hanoiMover source using dest 1
                         ++ hanoiMover using source dest (n-1)

This version is essentially a higher-order functional composition of my original hanoi.hs mentioned at the beginning of this blog post.

Thanks to augustss for pointing out this observation; I’ll try to write my functions in a more functional style hereinafter.

P.P.S.

Another commentator, Jedai, has been generous enough to indicate that my version of hanoi can be rewritten entirely without parentheses. Per Jedai’s suggestion, I have rewritten hanoi.hs as follows:

-- hanoiHelperRichSansParens.hs
-- Haskell function to compute the Towers of Hanoi problem recursively, 
-- using a helper function and the '$' operator to take a function and 
-- an argument, and accordingly save typing parentheses, rewritten
-- without parentheses
-- 
-- Originally based on hanoiHelperRich.hs, a Haskell function to compute
-- the Towers of Hanoi problem recursively, by Benjamin L. Russell,
-- dated April 13, 2009, at 20:13; 
-- revised based on a comment from Jedai, dated April 18, 2009, at
-- 03:21, (see http://dekudekuplex.wordpress.com/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/#comment-57),
-- in response to my blog post "Climbing the Towers of Hanoi with
-- Haskell-style Curry from a Monadic Container (While Sparing the 
-- Sugar!)," dated April 13, 2009, at 19:59 (see
-- http://dekudekuplex.wordpress.com/2009/04/13/climbing-the-towers-of-hanoi-with-haskell-style-curry-from-a-monadic-container-while-sparing-the-sugar/)
--
-- Copyright(C) April 20, 2009, at 19:25, 
-- by Benjamin L. Russell
-- 
-- This program is free software; you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation; either version 2 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
--
-- You should have received a copy of the GNU General Public License
-- along with this program; if not, write to the Free Software
-- Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

hanoi :: Integer -> IO ()
hanoi n = hanoiHelper n "A" "B" "C"

hanoiHelper :: Integer -> String -> String -> String -> IO ()
hanoiHelper n source dest using
                | n == 1 = putStrLn $ "Move disc from " ++ source ++ " to " ++ dest ++ "."
                | otherwise = hanoiHelper (n-1) source using dest
                                      >> hanoiHelper 1 source dest using
                                           >> hanoiHelper (n-1) using dest source

A Correction to “Too Much is Not Enough: The Revised^6 Report on the Algorithmic Language Scheme (R6RS)”

In my previous blog entry, I had listed Jacob Matthews and Robert Bruce Findler as having been on the list of authors for the Revised^6 Report on the Algorithmic Language Scheme, but last month, Robby Findler pointed out in a comment that neither of these two authors had been responsible for decision-making; rather, they had only been authors of the formal semantics thereof.

Therefore, I am removing them from the list of people responsible for decision-making for R6RS.

My apologies for the late correction.

Too Much is Not Enough: The Revised^6 Report on the Algorithmic Language Scheme (R6RS)

On September 26, 2007, the Revised^6 Report on the Algorithmic Language Scheme was released. Normally, a new standard for Scheme is greeted with applause, but this time, the revision sparked a great controversy. The Scheme community became divided between pro-R6RS and anti-R6Rs factions, and some members even decided to leave programming language theory completely at least partly because of this change. As Nils M. Holm has mentioned,

A lot has happened since the release of the previous edition of Sketchy LISP. The Six’th Revised Report on the Algorithmic Language Scheme (R⁶RS) was ratified and Scheme is no longer the language it used to be.

Why not? Consider this graph provided by Grant Rettke. Looking at the graph, it is remarkable how there is a sudden break in continuity between most of the members of the list of authors for R2RS – R5RS, and those for R6RS. Specifically, the following authors were in common between R2RS – R5RS, but suddenly disappeared in R6RS:

Chris Hanson
Chris Haynes
Dan Friedman
David Bartley
Don Oxley
Eugene Kohlbecker
Gary Brooks
Hal Abelson
Jonathan Rees
Kent Pitman
Mitchell Wand
Norman Adams (or Norman I Adams IV, assuming this name references the same author)
Robert Halstead
William Clinger

Instead, we suddenly see the appearance of the following authors for R6RS, who had never appeared in any of R2RS – R5RS:

Anton Van Straaten
Jacob Matthews
Matthew Flatt
Michael Sperber
Robert Bruce Findler

In fact, the only person common in the lists between R3RS – R5RS (according to the chart, he was not an author for R2RS) and R6RS is Kent Dybvig.

What happened to all the previous authors, and who are these new authors?

Apparently, at least some of the previous authors quit the board, possibly because of a disagreement over the new standard. As for the new authors, I know of both Matthew Flatt and Robert Bruce Findler from PLT Scheme. They are members of the PLT Research Group, and they regularly post on the plt-scheme mailing list. (They have both been very helpful on many occasions, so I have no qualms against them personally; I am just trying to analyze their motivations for R6RS.) They are both also among the authors for HtDP. They are also among the co-authors for the influential paper “The Structure and Interpretation of the Computer Science Curriculum.” According to that paper (see pp. 6-7, in section “3.1 Functional and object-oriented programming”), they write as follows:

Functional programming and object-oriented programming differ with respect to
the syntax and semantics of the underlying languages. The core of a functional lan-
guage is small. All a beginning programmer needs are function definition, function
application, variables, constants, a conditional form, and possibly a construct for
defining algebraic types. In contrast, using an object-oriented language for the same
purposes requires classes, fields, methods, inheritance in addition to everything that
a functional language needs….

Using a functional language followed by object-oriented language is thus the
natural choice. The functional language allows students to gain confidence with
program design principles. They learn to think about values and operations on
values. They can easily comprehend how the functions and operations work with
values. Better still, they can use the same rules to figure out why a program pro-
duces the wrong values, which it often will. Teaching an object-oriented language
in the second course is then a small shift of focus….

I.e., Flatt and Findler believe that teaching functional programming should be followed by teaching object-oriented programming. This concept, however, is not shared by all educators. In particular, Paul Hudak, one of the designers of the Haskell programming language, writes on the Haskell-Cafe mailing list as follows on a related issue (see “[Haskell-cafe] a regressive view of support for imperative programming in Haskell“:

All of the recent talk of support for imperative programming in Haskell
makes me really nervous. To be honest, I’ve always been a bit
uncomfortable even with monad syntax. Instead of:

do x <- cmd1
y <- cmd2
…
return e

I was always perfectly happy with:

cmd1 >>= \x->
cmd2 >>= \y->
…
return e

Functions are in my comfort zone; syntax that hides them takes me out of
my comfort zone.

In my opinion one of the key principles in the design of Haskell has
been the insistence on purity. It is arguably what led the Haskell
designers to “discover” the monadic solution to IO, and is more
generally what inspired many researchers to “discover” purely functional
solutions to many seemingly imperative problems. With references and
mutable data structures and IO and who-knows-what-else to support the
Imperative Way, this discovery process becomes stunted.

Well, you could argue, monad syntax is what really made Haskell become
more accepted by the masses, and you may be right (although perhaps
Simon’s extraordinary performance at OSCOM is more of what we need). On
the other hand, if we give imperative programmers the tools to do all
the things they are used to doing in C++, then we will be depriving them
of the joys of programming in the Functional Way. How many times have
we seen responses to newbie posts along the lines of, “That’s how you’d
do it in C++, but in Haskell here’s a better way…”.

While Hudak contrasts imperative vs. functional, as opposed to object-oriented vs. functional, the basic issue is the same: Should functional programming be treated as a separate paradigm by itself (as “the Functional Way” vs. “the Imperative Way” (or maybe even “the Object-oriented Way”)), or should it be combined with a different paradigm (be it imperative or object-oriented, the issue is the same). Or even (according to some educators), should there even be an issue of “paradigm” at all?

This is an issue of basic teaching philosophy. As an example of the third viewpoint, Shriram Krishnamurthi writes on the plt-scheme mailing list as follows (see “[plt-scheme] Re: More pedagogic stuff“:

Besides the simplistic
reasoning, I am opposed to the whole idea of programming languages (or
even much of programming) being organized around “paradigms”. Here is
a short and intentionally somewhat provocative article that I recently
wrote about this:

http://www.cs.brown.edu/~sk/Publications/Papers/Published/sk-teach-pl-post-linnaean/

In the referenced page, Krishnamurthi writes as follows:

Programming language “paradigms” are a moribund and tedious legacy of a
bygone age. Modern language designers pay them no respect, so why do our courses
slavishly adhere to them? This paper argues that we should abandon this method of
teaching languages, offers an alternative, reconciles an important split in programming
language education, and describes a textbook that explores these matters.

In the referenced paper (see “Teaching Programming Languages in a Post-Linnaean Age,” Krishnamurthi writes (see p. 1, third paragraph):

Most books
rigorously adhere to the sacred division of languages into “functional”, “imperative”, “object-oriented”,
and “logic” camps. I conjecture that this desire for taxonomy is an artifact of our science-envy from the
early days of our discipline: a misguided attempt to follow the practice of science rather than its spirit.
We are, however, a science of the artificial. What else to make of a language like Python, Ruby, or Perl?
Their designers have no patience for the niceties of these Linnaean hierarchies; they borrow features as they
wish, creating melanges that utterly defy characterization.

Ultimately, it seems that this issue boils down to a matter of taste.

This is usually not a problem, so long as this taste is confined to a particular implementation. The problem with R6RS is that it is not just an implementation; it is a standard that can affect all implementations. R6RS, compared to previous revisions, makes a dramatic number of changes to the Scheme standard. Each one, individually, is not such a big problem; it is the entirety of all these changes taken together without sufficient discussion that is the problem.

The members of the board had to vote for all the changes taken together, rather than each one separately. A standard usually should require a consensus; however, this consensus was not really achieved in the case of R6RS (read through the reasoning behind both the “yes” and “no” votes in the “R6RS Ratification Vote,” and you will see the scope of the division).

Some of the main points of this division seem to be the following (apologies to those whose votes are not listed below; I have listed only the votes of names that sounded familiar to me, but there were many other significant votes, which were omitted not because of lack of significance, but because of lack of space and time):

the module system (see votes by Chris Hanson and Taylor R Campbell)

SYNTAX-CASE (see the vote by Chris Hanson above)

the switch to case sensitivity (see the vote by Jonathan Rees)

defining too many features as part of the language, rather than on top of the language (see the vote by Nils M Holm)

lack of time to change the draft to meet the deadline of the ratification draft (see the vote by Shiro Kawai)

too long description of the specification (thrice the previous one); restrictions on implementation design that impede future development of the language in the areas of numbers, text manipulation & Unicode, and the module system; overreach of the module system’s definition (see the vote by Taylor R Campbell)

Even some of the “yes” votes list “imperfections” that “troubled” them:

apparent inflexibility of the library system, and absence of a facility analagous to Common Lisp’s reader macros (see the vote by Alexey Radul)

In sum, it seems that R6RS was at least partly motivated by a perceived need by at least some of the new authors for a standard of Scheme that would help ease the transition between the functional and object-oriented paradigms. Apparently, at least some of the authors perceived that adding more features to the core language, instead of defining a small core language and adding features on top of the language, would help with this transition.

Another problem was lack of time. R6RS seems rather rushed compared to previous specifications. There probably should have been more discussion before finalizing the specification. In particular, there should have been some means of voting on each potential feature separately, instead of on all of them together. It is quite possible for each feature alone to be quite useful, but for the combination of all of them put together suddenly at once to be quite problematic.

(This entry an adaptation of my post “Re: History of Scheme People,” dated “Thu, 26 Feb 2009 15:45:33 +0900,” on the USENET newsgroup comp.lang.scheme.)

Motivating Category Theory for Haskell for Non-mathematicians

The Issue:  Why Study Category Theory?

Two days ago, there was another interesting post by Andrzej Jaworski, entitled “[Haskell-cafe] Mathematics for Uninterested,” dated “Sat, 17 Jan 2009 05:15:25 +0100,” on the Haskell-cafe mailing list on the Haskell programming language, offering an explanation of why mathematics is important for learning Haskell. In particular, he wrote:

MATHEMATICS_IS_ABOUT_SIMPLIFYING_THINGS.

MATHEMATICS = MATHEMATICAL_KNOWLEDGE + FORMAL_METHODS_of_THINKING

You need only the second part for Haskell.

He then continued:

… Category Theory generalizes our mathematical experience along the line that we know
more that we can prove.

Nevertheless, many non-mathematicians continue to have much difficulty in motivating study of category theory.  Some regard it as too theoretical.  Others regard it as too abstract.  And still others regard it as too dry.

While I cannot argue too much against the second point (indeed, category theory has been nicknamed “abstract nonsense,” although not necessarily pejoratively), and cannot truly deny the first for those who do not prefer theory, I have something to say from personal experience, as a student who overcame math phobia to appreciate beauty in mathematics, about the third.

Each student learns differently.  Some learn best by seeing examples.  Some learn best by studying theory.  Still others learn best by actually solving problems.

Case Study:  My Personal Experience in Approaching Mathematics

Several years ago, when I was still living in Manhattan, I read an article in a local newsletter about how different students had different learning styles in primary (and possibly secondary) school, and how putting different students into the wrong type of class inhibited their learning.  In particular, the article discussed how most students in the classes could be grouped into either of two different learning styles:  those who learned by example, and those who learned by theory.  Students who learned by example needed to see concrete examples of the mathematics in action in order to infer the reasoning; conversely, students who learned by theory learned best by studying the general theory from which to deduce specific applications.  Neither style was correct; they were simply different, and suited different types of students.

The same can probably be said for learning category theory.  Personally, I learn best from a combination of first studying theory, and actually applying the theory to incrementally more sophisticated problems.  Without the theory, I cannot understand the examples, but without actually applying the theory, I tend to forget about it very quickly.  Applying the theory, especially in a creative manner, makes it stick in my brain.

However, although I eventually was able to major in computer science, getting there was a long, arduous, grueling odyssey.  The most difficult part was conquering a required course in the design and analysis of algorithms.  I had come to college from a self-educated background, studying on my own since fifth grade in elementary school without any teacher, using only books, because of family circumstances.  In the end, I wound up studying throughout my secondary school years at home.

However, my interests had been in writing and multimedia applications.  As a result, prior to coming to college, while I had had extensive practice in writing, I had had minimal exposure to mathematics.  My first exposure to college-level mathematics resulted in an outbreak of math phobia.

Nevertheless, I still wished to study something related to computers in college.  Because the school happened to be a research-oriented school with a theoretically-oriented faculty, the only computer-related topic available happened to be computer science, and the focus was on theory.

Theoretical computer science happens to have a heavy focus on mathematics.  However, I happened to be struggling with math phobia.  I needed to find something interesting about mathematics if I was to remain in computer science.

Fortunately, one very generous mathematics student offered to tutor me gratis once per week over one summer.  He gave me what he termed “an elementary course from an advanced viewpoint.”  He started out from axiomatic set theory, focusing on lemmas and proofs of theorems, and gave me an intuitive grasp of such elementary concepts as set comprehension, power sets, ordered pairs, and Cartesian products.  I later learned about Russell’s paradox, and found it rather interesting.  At the end of the summer, I was able to take and pass an undergraduate course at my college in axiomatic set theory.  Then I discovered Gödel, Escher, Bach: an Eternal Golden Braid, was fascinated, and the next semester, I proceeded on to pass recursive function theory.  Then I took a course in automata theory.  Then I took a course (albeit in the philosophy department) in meta-logic.  Then I took a graduate-level course in recursion equations (domain theory).

After then taking a year’s leave of absence to study discrete mathematics for computer science outside of my official curriculum, I was able to return and eventually pass the required course in the design and analysis of algorithms.  The next semester, I then took an additional course in advanced algorithms, which turned out to be significantly less of a hassle than the first course in algorithms (the exercises were more abstract, but the workload was considerably less, so I went to the library and did some research for each problem set).  One of my favorite courses later wound up being one in formal semantics of programming languages, where I was exposed to this fascinating creature, the lambda calculus.

Yet somehow along the way … I forgot how to program well.  I had to struggle through another required course in systems programming in C, and this time acquired programming phobia, which I had not had before.  Oh dear, I had forgotten how to use pointers in coding linked lists!  I only recovered after auding a course using Scheme to teach computer science under a professor who also taught Haskell.  Then I audited another course under this professor in Haskell.  Thank goodness!  No more pointers, no more memory management!  Instead, higher-order functions!

A Short, Thin, Elementary, Yet Influential Book and Its Approach

One of the most influential books in my struggle to conquer algorithms was a most unassuming, very thin, informal book called Naive Set Theory, by Paul R. Halmos.  This book had no explicit exercises marked as such, and the treatment was almost conversational in tone, yet almost every sentence was an implicit exercise in abstract thinking.  Each chapter was only three to five pages long, with almost no equations, and the entire book was only about a hundred pages long.  The covers together were barely thicker combined than the text.  Yet it still covered the following topics:

the Axiom of Extension
the Axiom of Specification
unordered pairs
unions and intersections
complements and powers
unordered pairs
relations
functions
families
inverses and composites
numbers
the Peano Axioms
arithmetic
order
the Axiom of Choice
Zorn’s Lemma
well ordering
transfinite recursion
ordinal numbers
sets of ordinal numbers
ordinal arithmetic
the Schröder-Bernstein Theorem
countable sets
cardinal arithmetic
cardinal numbers

Imagine covering an entire topic in mathematics with almost no equations, and no explict exercises, and only three to five pages per chapter!  This was easily one of the shortest books I ever read in college, yet one of the most influential: Not only did it resolve the math phobia, but it also imbued me with an appreciation for elegant proofs, and hence for beauty in mathematics.

A Related Topic:  Computability Theory

Another experience that helped in my endeavor was an independent seminar with one researcher in automata theory (it was actually this experience which eventually led to my auditing a course in this subject).  My employer for one summer was a programmer who had graduated from the same university.  He helped me set up an independent once-a-week seminar (actually a private tutorial) covering the book Elements of the Theory of Computation (first hardcover edition), by  Harry R. Lewis and Christopher Papadimitriou.  I would read the book, collect questions, and bring them to the seminar every week.  This book covered such topics as computability, the diagonalization lemma, unsolvability, finite state automata, Turing machines, mathematical logic, and other related topics.  What I liked about this book was the aspect that, although it gave a very formal, abstract treatment to computability theory, otherwise it did not assume any specific knowledge of any area of mathematics.

I think that a book similar to the above two for category theory would be highly useful, at least for students with the same learning pattern as myself.  For such students, I believe that what is most important is the intuition; the formalism can come later.  Mathematics is not about formalism; it is about insight: insight into patterns and structure, and the beauty that comes with such patterns.  While a book with many exercises would probably be necessary at some point, for a first course in category theory for a non-mathematician, an approach similar to Halmos’ would seem most effective.

Set Theory vs. Category Theory:  The Conflict in Approach

The only problem with recommending a book on set theory to a student of category theory is that the approaches do not overlap. Set theory studies what is inside sets; category theory studies what is outside them.

Specifically, set theory starts out by defining the empty set, then defining basic axioms, and then defining certain operations on sets and functions operating on sets in leading up to lemmas and theorems about properties of sets.  However, the focus is essentially on what is inside the sets.

However, category theory ignores what is inside, and instead focuses on structure-preserving mappings (known as “homomorphisms”) between different sets having a specific structure.  These homomorphisms lead to theorems about the structure of the sets.  Thus, it is these mappings in category theory that are the focus, not explicitly what is inside the sets.  This is the origin of the nickname of “abstract nonsense” in reference to category theory.

Therefore, there is a risk that exposing a new student of Haskell first to set theory could actually confuse the student upon subsequent exposure to category theory. Therefore, I might substitute instead an elementary introduction to category theory with an informal, somewhat conversational tone, such as the following:

Conceptual Mathematics: A First Introduction to Categories
by F. William Lawvere and Stephen Hoel Schanuel
Cambridge: Cambridge University Press, 1997
As discussed in my blog entry “Learning Haskell through Category Theory, and Adventuring in Category Land: Like Flatterland, Only About Categories,”this is an elementary introduction to category theory, with a conversational tone, using such examples as Galileo and the flight of a bird for illustration.

Advanced Topics for Further Study

Once the student has had a taste of category theory, there are two possible alternatives:  Either broaden the topics, or deepen them.  The latter has already been discussed in my above-mentioned blog post “Learning Haskell through Category Theory, and Adventuring in Category Land: Like Flatterland, Only About Categories“; here I discuss the former.

As mentioned above, automata theory is one possibility for advanced study for students who have acquired a taste for theory and wish to explore more:

Elements of the Theory of Computation (first hardcover edition)
by Harry R. Lewis and Christopher Papadimitriou
New Jersey: Prentice Hall, Inc., June 1981
As discussed above, a formal, rigorous treatment of the theory of computation. The book assumes the ability to reason abstractly, but does not assume familiarity with any specific areas of mathematics. Most readers either love or hate this book, depending on whether they are theoretically-inclined.

Another possibility is recursive function theory:

Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science (Computer Science and Scientific Computing)
by Martin Davis, Ron Sigal, and Elaine J. Weyuker
San Francisco, California: Morgan Kaufmann Publishers, 1994
This book, like Elements of the Theory of Computation, is formal, but does not assume any specific background in mathematics.  One of the authors of this book, Ron Sigal, used to be my professor for set theory, recursive function theory, and recursion equations (domain theory) in college. He was friendly and approachable, had an exceptionally clear teaching style, and usually spent the first class in an interesting lecture discussing the historical background of the subject.

Still another possibility is my nemesis, the design and analysis of algorithms:

Compared to What?: An Introduction to the Analysis of Algorithms (Principles of Computer Science Series)
by Gregory J.E. Rawlins
New York: W. H. Freeman, November 15, 1991
This was my favorite book on algorithms in college, and played an instrumental role in allowing me to pass this subject. Without this book, I probably would have had a much more difficult time in clearing this subject. This book approaches each algorithm from the perspective of how the algorithm is arrived at, rather than just handing the solution ready-made, interspersing numerous entertaining illustrations and quotes from works by Lewis Carroll. I further wrapped this book in kaleidoscopic bookwrap to strengthen the feeling of being in algorithm wonderland while reading this book, and the effect worked like a charm: I learned the algorithms, finally passed the course, and completed the major.

Introduction to Algorithms, Second Edition
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Cambridge, Massachusetts: The MIT Press, September 1, 2001
This is the second edition of a classic work in the subject. It provides a rigorous theoretical treatment of algorithms. The first edition of this book forced the author of this blog to undertake a seemingly never-ending journey through set theory, discrete mathematics, recursive function theory, automata theory, meta-logic, and recursion equations (domain theory) in order to clear the topics covered by this book. I haven’t read the second edition yet, but the first edition was very complete and thorough, and was basically a mathematical encyclopedia on algorithms, complete with a brief introduction to prerequisite topics, detailed development of proofs, numerous exercises that led to other parts of the main text, numerous starred exercises of special difficulty (my professor hired a student who did all the starred exercises on his problem sets as a summer research intern), detailed pseudocode, analysis of the pseudocode, proofs of the analysis of the pseudocode, and highly detailed illustrations covering details of the algorithms and their proofs. Of course, this book has no solutions. Hey, who needs solutions? Nobody said you needed sleep, right?

The Art of Computer Programming (currently, Volumes 1 to 3 and Fascicles 0 to 4 of Volume 4, with Volume 5 planned for release in 2015, and Volumes 6 and 7 planned for later release)
by Donald E. Knuth
Reading, Massachusetts: Addison-Wesley, 1997 to 2006 and pending
The original classic work on the design and analysis of algorithms.  Still in progress.  Originally begun in 1962, written by compiler expert Donald E. Knuth.  Volume 1 covers fundamental algorithms, volume 2 covers seminumerical algorithms, volume 3 covers sorting and searching, volume 4 covers combinatorical algorithms, volume 5 is scheduled to cover syntactic algorithms, volume 6 is scheduled to cover the theory of context-free languages, and volume 7 is scheduled to cover compiler techniques.  Exercises range in difficulty from “warm-up” exercises to research problems.

One last topic is algebra, for which there is reputedly a very approachable work focusing on a limited scope of topics and exploring them to great depth:

Topics in Algebra
by I. N. Herstein
Xerox Corporation, 1975
Although I haven’t read this book, it has earned very high reviews for exposition and flow. The book is reputedly designed so that a few basic ideas are focused on, and problems in them explored, so that each new topic flows seemlessly from the previous one.

Conclusion

Let students take the book on the subway, train, or bus, and have them think about the categories in their sleep!  Gradually, their curiosity will be piqued, and they will understand categories.  Then they can read a second book with many exercises.  But while they still have curiosity, let them at least visualize and juggle the categories in many ways in their heads before forcing them off!  The more easily they can digest their first book, the more likely their curiosity will stay.

Learning Haskell through Category Theory, and Adventuring in Category Land: Like Flatterland, Only About Categories

Two days ago, there was an interesting post by Andrzej Jaworski, entitled “[Haskell] Teach theory then Haskell as example,” dated “Wed, 14 Jan 2009 04:37:33 +0100,” on the Haskell mailing list on the Haskell programming language, recommending that Haskell be taught “on most abstract terms in a framework of higher order logic, types and CT right from the start.”  While I agreed with the gist of his post, I hadn’t found an appropriate publication on category theory that addressed the subject at the proper pace, level, and perspective.  Most publications did not explain enough detail, assumed too many topics not covered, or did not explain the concepts in a manner which would allow me to form a visual framework of reference in my mind.  In my response, I listed the following publications on category theory, a branch of mathematics which forms a theoretical framework for Haskell. (Author names and dates have been added, explicit URL’s replaced by hyperlinks in titles, and descriptions expanded, for referential convenience. In addition, I have added one additional book entry for cross-referential purposes.):

Category Theory Books:

Conceptual Mathematics: A First Introduction to Categories (Paperback)
by F. William Lawvere (author) and Stephen Hoel Schanuel (author)
Cambridge: Cambridge University Press, 1997
An elementary introduction to category theory

An introduction to category theory in four easy movements
by A. Schalk (author) and H. Simmons (author)
Manchester: A. Schalk and H. Simmons, October – December, 2005
A somewhat informal, reportedly in-depth introduction to category theory, which some students have described as being intricately layered. Personally, I like Harold Simmons style, because it seems to have more personality than that of many other authors on category theory. Sometimes he is actually funny; e.g., he writes (see p. 6),

“In the original examples of categories the arrows were morphisms which were then called homomorphism, and it wasn’t realized that this family could be very large. (Some out and out category theorists still don’t realize the significance of this. On the other hand, some off the wall set theorists don’t realize the significance of category theory.)”

I’ve heard of the UNIX wars and the editor wars, but now we have the category theory vs. set theory wars! The more some things change, the more they stay the same….

Category Theory by Magic: A short introduction to the basics of category theory
by Harold Simmons
Manchester: Harold Simmons, November 29, 2008
A somewhat more advanced text than An introduction to category theory in four easy movements, intended specifically for “postgraduate students,” but written in an exceptionally clear style.

Toposes, Triples and Theories
by Michael Barr and Charles Wells
Michael Barr and Charles Wells, 2000
An often-referenced introduction to category theory, intended for graduate students, reportedly
discussing monads as “triples.”  This book is a sequel to Category Theory for Computing Science, by the same author. This is one of the publications listed in the bibliography by Simmons in Category Theory by Magic: A short introduction to the basics of category theory.

Category Theory for Computing Science (Third Edition)
by Michael Barr and Charles Wells
Hertfordshire, U.K.: Prentice Hall International (UK) Ltd., 1999
Prequel to Toposes, Triples and Theories, “written specifically to be read by researchers and students in  computing science.”    Apparently, only available in dead-tree format.  Can be ordered from Centre de recherches mathématiques, or by e-mail to crmbooks@crm.umontreal.ca.  Often cited in the literature.

Categories and Computer Science
by R. F. C. Walters
Cambridge: Cambridge University Press, August 1992
Reportedly a straightforward introduction to category theory, with many examples from computer science

Arrow, Structures and Functors – The Categorical Imperative (no hyperlink available)
According to the HaskellWiki page on category theory, an out-of-print book covering monads and the Yoneda lemma, with very little prerequisite knowledge

Category Theory Lecture Notes:

Category Theory Lecture Notes for ESSLLI
by Michael Barr and Charles Wells
Michael Barr and Charles Wells, 1999
Condensed version of Category Theory for Computing Science, discussing category theory from a computer science perspective

A Gentle Introduction to Category Theory – the calculational approach
by Maarten M. Fokkinga
Amsterdam: M. M. Fokkinga, 1992 (version of June 6, 1994)
Another set of lecture notes referenced on the HaskellWiki page on category theory

Categorical Programming with Examples in Haskell:

Categorical Programming with Inductive and Coinductive Types
by Varmo Vene
Tartu, Estonia: Varmo Vene, 2000 (Ph.D. dissertation)
A thesis on categorical programming, exploring inductive and coinductive types, and several programming constructs related to them in Haskell

In conclusion, I stated as follows:

I would believe that having specific Haskell code to help interact
with the categorical examples would help to motivate study of the
abstract theory for many programmers.  One problem that many people
have with studying abstract theory in isolation is that they often
tend to lose motivation unless they can see how the theory directly
relates to and influences the semantics and data structures in the
code.  Having specific examples of Haskell code to tie together
immediately with the abstract theory would most likely help to
motivate and maintain interest.

Then I discovered a similar thread in the USENET newsgroup comp.lang.haskell which had originated two days earlier, entitled “Book recommendations on underlying theory,” dated “Sun, 11 Jan 2009 15:11:40 -0800 (PST),” in which a reader nicknamed “grimey” was asking for recommended readings on the theory behind Haskell.  Grimey described himself as a programmer who had “studied physics at the undergrad level,” and whose mathematical background included “Diff & Integ. Calc, Linear Algebra, Diff Eq, Advanced (Vector) Calc, [and] Complex Analysis.”  In particular, he added,

Although the Vector Calc class was particularly difficult
for me and sort of “took the wind out of my sails” and leaving me
adrift on the sea of mathematics for a long time.  I always wanted to
continue on with more abstract math, like algebra and group theory, to
gain understanding of the beauty behind quantum physics; but for
various reasons, that didn’t happen.  Anyway years later I still use
Linear Algebra and Diff Eq quite frequently for work, and have a good
practical engineer’s grasp of those topics.  I use advanced calculus
less frequently and I use quaternions for very practical, non-
theoretical way for rotation sequences in 3D.  I am an expert C/C++
programmer.

He then mentioned the following books as two that had “piqued [his] interest,” before asking for further suggestions:

Topics In Algebra
by I.N. Herstein
Xerox Corporation: 1975

Lambda-Calculus and Combinators
by J. Roger Hindley and Jonathan P. Seldin
Cambridge: Cambridge University Press, 2008

In my response linking the two threads, I mentioned Andrzej Jaworski’s response to my earlier posting in the first thread, in which he had replied in part that:

[T]here are many very good
articles addressing specific issues of Haskell's theoretical foundations (e.g.
http://www.cs.ut.ee/~varmo/papers/thesis.pdf).  They however always assume more than they target to
explain making student turn around them like a dog not knowing which ball to catch first.

I.e., the problem was that many such papers depended on parts of other papers, which either depended on other parts of the first paper, or on parts of still other papers.  Then I mentioned a response to this issue that I had received in a private e-mail message from a reader of the first thread, in which that reader had written that:

… the problem “comes from trying to use academic papers as textbooks, a
purpose for which they’re not usually designed.”

I then added that this was the gist of the problem, and, as a possible solution, added a dead-tree-based book that I had read about earlier (already mentioned above):

Conceptual Mathematics: A First Introduction to Categories (Paperback)
by F. William Lawvere and Stephen Hoel Schanuel
Cambridge: Cambridge University Press, 1997
An elementary introduction

I added:

This book is reputed to be interesting even to non-mathematicians at a
philosophical level.  I myself have purchased a copy.

Then, on an afterthought, in an additional post immediately afterwards, I added that what would be even better would be a mathematical storybook (separate links to the storybooks hyperlinked in the following quoted portion):

What would be especially interesting would be an introductory storybook on category theory:  a book similar to, say, Flatland, by Edwin Abbott Abbott, or even Flatterland, by Ian Stewart.  These books would elevate category theory out of the realm of dry equations into a story which would keep me awake with suspense reading through the night.

Yes!  What we need is Category Land:  Like Flatterland, Only About Categories.  If only a book were so.  Any suggestions?

Refal: Recursive Functions Algorithmic Language

Last month, while reading a post by Cyril Slobin, dated “Fri, 12 Dec 2008 09:20:35 +0300,” in the thread “Beginnings – History of Declarative Languages” on the Qilang mailing list on the Qi programming language, I came across a reference to an unusual functional programming language called “Refal.”  “Refal” is short for “Recursive functions algorithmic language,” and is a language designed by Valentin Turchin for symbol manipulation.

Refal is based on pattern matching, and unlike Prolog, pattern matching in Refal works forwards, not backwards.

To illustrate a Refal program in action, let us consider the problem of determining whether a given string is a palindrome.  Here is a formal definition of a palindrome (quoted from “Section 1.1: A Simple Function Definition” of the online manual “REFAL-5: programming guide & reference manual“):

1. An empty string is a palindrome.
2. A string of one symbol is a palindrome.
3. If a string starts and ends with the same symbol, then it is a palindrome if and only if the string which remains after the removal of the first and the last letters is a palindrome.
4. If none of the above are applicable, the string is not a palindrome.

Based on the above definition, here is an example of a typical Refal program for determining whether a given string is a palindrome:

Pal { = True;
     s.1 = True;
     s.1 e.2 s.1 = <Pal e.2>;
     e.1 = False;  }

Here, “Pal” is the function name, followed by a definition.  In the definition, the first line matches a blank string with “True.”  Thus, an empty string is a palindrome.

In the next line, “s.1″ is a free variable of type symbol, which matches any single symbol, but only a single symbol, with “True.”  (The ‘1′ here is a subscript.)  I.e., such symbols as ‘a,’ ‘1,’ ‘%,’ etc. match with “True,” and hence are palindromes as well.

In the following line, “e.2″ is a free variable of type expression, where an expression is the most general data type in Refal, possibly being a string of symbols.  This line matches any single symbol, followed by any expression, followed by the same single symbol.  Angular brackets denote a function call, so “<Pal e.2>” denotes a recursive call of Pal on “e.2.”  Here, “e.2″ is just the inner expression, sans the outer pair of identical symbols.  Thus, “aba” will match and then recursively call Pal on the inner ‘b,’ “abca” will call on the inner “bc,” “ab1a” will call on the inner “b1,” and so forth.

In the last line, any other expression which does not match the other two lines above it is not a palindrome.  E.g., “ab” is not, nor is “a%,” nor is “a1,” nor are any other similar expressions that do not match the above two lines.

In practice, Pal is called with a line such as the following at the top of a .ref Refal source file:

$ENTRY Go { = <Prout <Pal ‘tattarrattat‘>> }

Here, “tattarrattat” can be replaced by any other palindrome.  (I haven’t yet proceeded far enough to explain this line in the manual, so I shall leave explanation of this line for a possible alternative time.)

The above-referenced Refal manual also includes a reference to an online Refal compiler for viewing, editing, compiling, and executing Refal snippets in a Web browser.  This compiler even saves source code in a temporary file between Web sessions!

There is also Refal-SciTE, a compact combined GUI-based editor, REPL, and compiler, based on Refal-5 and the SciTE editor.

What I find especially notable about Refal is its emphasis on symbol manipulation, instead of numeric computation.  Many other functional languages tend to focus more on numeric computation; however, one of my original interests in programming back in the 1980’s, when I was still reading such ancient computer magazines as Byte, was in simulating human verbal communication.  I fondly remember one article back at the time (unfortunately, I do not remember in which magazine the article had been published) about somebody who had written a simple program (I think that it had actually been in a dialect of BASIC) to create sentences using grammatical units stored in a dictionary which was part of the program.

This person reportedly spent just one afternoon writing the program, and then sat back for several hours as he watched, fascinated, as the program output sentence after sentence of original prose, in which some sentences were quite unusual and unlike anything that a human being would naturally come up with.  For example (I am coming up with these examples on my own, based upon what I remember of the kinds of examples given in the article), some possible sentences created by the program could be the following:

Fish swim in cheese under umbrellas.

Nelson coughed dynamite eating raw fish.

Jack sweated programs sleeping monkeys.

These are all grammatically correct English sentences, but unlike anything that most English speakers would come up with on their own, because the ideas behind them tend to be considered absurd or preposterous by most human English speakers.  However, a computer program that simply pulled grammatical units out of a dictionary and matched them at random in following grammatical rules could easily come up with such examples.  It is precisely the absurdity of such examples that caused their type to stick in my mind and to stay there for more than twenty years.

Other examples of functional programming languages focusing on symbol processing often cited are LISP and Scheme, but while Scheme remains one of my favorite functional programming languages, it lacks pattern matching.  Prolog has pattern matching, but employs backtracking instead of forward reasoning; in addition, Prolog programs tend to be very verbose compared to equivalent programs in such functional programming languages as Haskell.

Furthermore, recently my interests have been veering towards such statically typed programming languages as Haskell, Typed Scheme, and Qi, which have the advantage of increasing the probability that a program which successfully compiles does not need to be debugged (while decreasing the probability that a program hastily written will compile in the first place).

Moreover, I tend to enjoy the mental gymnastics of writing in a purely functional programming language, which does not allow side effects, such as Haskell; it is rather like trying to navigate through town while being limited to jumping over the tops of buildings and flying down their staircases like Spider-Man.  To stretch the analogy, the higher-order functions are the buildings, the spider webs are the maps, and the staircases are the recursive calls, which typically bottom out at the zeroth floor level.  There are fewer steps required, because each step jumps over an entire building, or maps over an entire series of buildings, but if you actually want to get in or out of a building, you need to do something special in binding yourself in returning through the door.

Yet while the purely functional style of Haskell often leads to interesting mental exercises in concocting elegant programs that do not rely on side effects, most Haskell examples tend to be focus on some form of numeric computation, rather than symbol manipulation; in addition, most discussion on Haskell seems to touch on some form of mathematics, often category theory; there is relatively little discussion focusing on symbol manipulation.  Refal, on the other hand, specializes in symbol manipulation, uses forward reasoning, and is concise.  I have barely started reading about Refal, but it seems a possibly interesting alternative for writing programs to deal with words and phrases.

A Cross-language Comparison of Monads in Haskell, O’Caml, and Qi

A few days ago, there was an interesting post by Rafael Gustavo da Cunha Pereira Pinto, dated “Mon, 5 Jan 2009 09:08:37 -0200,” on the Haskell-beginners mailing list on the Haskell programming language, referencing a monad tutorial for the O’Caml programming language that provided an alternative perspective in helping to illustrate monads in Haskell, mentioned in the thread “Yet Another Monad Tutorial.” In my response, I introduced an alternative monad tutorial for the Qi programming language, which also referenced Haskell.

Since the O’Caml monad tutorial mentioned design patterns as an alternative to category theory in forming a basis for describing monads, this reminded me of the book How to Design Programs, by Felleisen, Findler, Flatt, and Krishnamurthi, on Scheme, which led to a mention of Typed Scheme, which in turn led to a mention of Qi.  In turn, this led to a cross-language comparison of monad definitions in Haskell, O’Caml, and Qi, and their implications.

Hereinafter I have quoted parts of my response for reference (with minor edits to hyperlink various keywords, as opposed to leaving the link URL’s separate from their references):

The focus on design patterns brings to
mind the book How to Design Programs, by
Felleisen, Findler, Flatt, and Krishnamurthi, on Scheme, and the
recent dialect of Typed Scheme, as well as the
language Qi.

There is a somewhat similar tutorial on monads using Qi (see
“Programming Kung Fu Qi: Monads in Qi”).

For reference, I shall use the Haskell-based monad tutorial “All About
Monads” as a base for one of the Haskell versions of the examples.  Most of my
descriptions of the Haskell version will be borrowed from the
descriptions contained in the section there entitled “Meet the Monads”.

Let’s compare the Haskell version with the O’Caml version and a
hypothetical pure Scheme version:

Haskell version of monad rules (borrowed from the Qi-based tutorial):
>class Monad m where
>   return :: a -> m a
>   (>>=)  :: m a -> (a -> m b) -> m b

O’Caml version of monad rules (borrowed from the O’Caml-based
tutorial):
>module type MonadRequirements = sig
>    type ‘a t
>    val bind : ‘a t -> (’a -> ‘b t) -> ‘b t
>    val return : ‘a -> ‘a t
>end;;

Hypothetical pure Scheme version of monad rules (borrowed from the
Qi-based tutorial):
>   (pipe (lift x) f)   = (f x)
>   (pipe m lift)       = m
>   (pipe (pipe m f) g) = (pipe m (lambda (x) (pipe (f x) g))

The Haskell version is the most concise.  The “return” and “(>>=)”
(”bind”) operations in Haskell correspond to the “return” and “bind”
operations in the O’Caml version, and to the “lift” and “pipe”
operations in the hypothetical pure Scheme version.

In the Haskell version, “m” is the type constructor, “return” is an
operation that creates a value of the monad type “m a,” while “(>>=)”
(a.k.a. “bind”) is an operation that combines a value of that type “m
a” with a computation that produces values of that type to produce a
new computation for values of that type “(a -> m b) -> m b.”

Superficially, so far, the three versions seem fairly equivalent.

Now for examples of list monads:

Haskell version (adapted from combining the Haskell-based and the
Qi-based tutorials):
>instance Monad [ ] where
>   l >>= f = concatMap f l
>   []     >>= f = []
>   return x     = [x]

O’Caml version (borrowed from the O’Caml-based tutorial):
>module ListMonad = struct
>    type ‘a t = ‘a list;;
>
>    let bind lst f = List.concat (List.map f lst);;
>
>    let return x = [ x ];;
>end;;

Qi version (borrowed from the Qi-based tutorial):
>(define bind
>   [] _ -> []
>   [X | Xs] F -> (append (F X) (bind Xs F)))
>
>(define return
>   X -> [X]  )

Here we start to see some differences.

In the Haskell version, “return” simply creates a singleton list
(”[x]“), while “(>>=)” (i.e., “bind”) either returns a blank list “[]“
in the case of a blank list, or otherwise creates a new list
containing the results of applying the function to all of the values
in the original list “concatMap f l.”

In the O’Caml version, notice the “List.concat” operation.  After the
List.map operation, we are left with not a “‘a list”, but instead
with a “‘a list list”, so this is necessary to obtain the correct
type “‘a list.”  Otherwise, the reasoning is similar.

In the Qi version, we have split the monad into two functions:  “bind”
and “return.”  Splitting a large function into a smaller functions is
typical Scheme style.  Here, “return” simply pattern-matches an
element into a list containing that element, while “bind” either
pattern-matches an empty list “[]” followed by anything “_” to an
empty list “[],” or pattern-matches a list consisting of a car and a
cdr “[X | Xs],” followed by a function “F,” to “F” applied to “X,”
which is “(F X),” appended to a binding of the cdr of the list “Xs” to
the function “F.”

It seems that studying the Qi version may shed some insight into the
Haskell version by approaching it from a different perspective.  This
may also be true of the O’Caml version, but personally, I think that
the splitting of the monad into separate functions for “bind” and
“return” in the Qi version helps to differentiate it from the other
two versions, and hence offers additional insight into the nature of
the monad.

It may also be said that the use of both “List.map” and “List.concat”
in the O’Caml version offers similar insight.

Now for a pet peeve that I have with one of the examples in the O’Caml
monad tutorial:

>module SerialMonad = struct
>    type ‘a t = unit -> ‘a;;
>    let serial_mutex = Mutex.create ();;
>    let return x = (fun () -> x);;
>    let bind m g = (fun () -> (g (m ())) ());;
>    let access m =
>        Mutex.lock serial_mutex;
>        try
>            let r = m () in
>            Mutex.unlock serial_mutex;
>            r
>        with
>        | e ->
>            begin
>                Mutex.unlock serial_mutex;
>                raise e
>            end
>end;;
>
>This monad is basically identical to the previous FunMonad with the addition of the access function- which executes the
>process while holding the serial_mutex lock, which is always unlocked when the process completes (even if the process
>throws an exception). This forces all processes executing within a SerialMonad to be executed sequentially and serially
>(thus the name).

While a clear example, one problem that I have with this approach is
that the emphasis on forcing “all processes executing within a
SerialMonad to be executed sequentially and serially” reminds me of
the Imperative Way.  This brings to mind a posting by Paul Hudak on
Haskell-Cafe, entitled “a regressive view of support for imperative
programming in Haskell,” dated “Wed Aug 8 14:20:39 EDT 2007″,
in which he writes as follows:

>In my opinion one of the key principles in the design of Haskell has
>been the insistence on purity.  It is arguably what led the Haskell
>designers to “discover” the monadic solution to IO, and is more
>generally what inspired many researchers to “discover” purely functional
>solutions to many seemingly imperative problems.  With references and
>mutable data structures and IO and who-knows-what-else to support the
>Imperative Way, this discovery process becomes stunted.
>
>Well, you could argue, monad syntax is what really made Haskell become
>more accepted by the masses, and you may be right (although perhaps
>Simon’s extraordinary performance at OSCOM is more of what we need).  On
>the other hand, if we give imperative programmers the tools to do all
>the things they are used to doing in C++, then we will be depriving them
>of the joys of programming in the Functional Way.  How many times have
>we seen responses to newbie posts along the lines of, “That’s how you’d
>do it in C++, but in Haskell here’s a better way…”.

Although I greatly applaud alternative perspectives in learning
Haskell, I am somewhat suspicious of the emphasis on a
quasi-imperative approach.  One of the factors that initially
attracted me to Haskell in the first place was the emphasis on a
functional style.  In particular, purely functional code has a number
of advantages, including easier reasoning about program behavior,
easier formulation of proofs of correctness, and referential
transparency. Together with referential transparency comes
applicativity of formal methods of program analysis.  All this is lost
once the Functional Way is replaced by the Imperative Way.

Here, the Qi-based monad tutorial seems to focus more on examples that
use the functional approach, but perhaps this is just my opinion.

Comparative programming languages can be a very interesting topic.  If
anybody knows of any alternative monad tutorials in other functional
programming languages that could help to shed light on monads, please
feel free to mention them in this thread.

What’s interesting about this comparative programming languages-perspective is that it seems that studying both Haskell and Qi together may actually lead to learning Haskell more quickly than learning just Haskell alone, because the cross-language perspective helps to motivate and shed light on the trickier parts of Haskell semantics.

“Good Luck!,” Typed Scheme, and Curried Typed Scheme

Word of a strange variant of PLT Scheme known as “Typed Scheme” is spreading around (see http://www.ccs.neu.edu/home/samth/typed-scheme/).  The idea is to add types to Scheme and make it more like Haskell.  Doing so is supposed to make it easier to debug procedures.

I couldn’t resist, so I decided to write up a sample Typed Scheme procedure.  Called “good-luck.ss” in regular PLT Scheme, it changes the output message depending on the input user name:

;; good-luck.ss
;; PLT-Scheme-specific program to wish a person good luck
;; 
;; Copyright(C) October 20, 2008, at 13:42, 
;; by Benjamin L. Russell

#lang scheme

(define (good-luck name)
  (if (string=? name "Nobody")
      (printf "You are ~a." name)
      (good-luck-helper name "Good Luck")))

(define (good-luck-helper a b)
  (printf "~a, ~a!" a b))

To run the Scheme source code above, simply type:

(good-luck "Benjamin")

You shall be rewarded with:

Benjamin, Good Luck!

Alternatively, typing

(good-luck "Nobody")

will result in:

You are Nobody.

Well, by itself, this isn’t any fun, so I then decided to translate this into a Typed Scheme procedure named “good-luck-typed.ss”:

;; good-luck-typed.ss
;; Typed Scheme version of good-luck.ss program to wish a person good luck
;; 
;; Copyright(C) October 20, 2008, at 13:46, 
;; by Benjamin L. Russell

#lang typed-scheme

(: good-luck-typed (String -> Void))
(define (good-luck-typed name)
  (if (string=? name "Nobody")
      (printf "You are ~a." name)
      (good-luck-helper-typed name "Good Luck")))

(: good-luck-helper-typed (String String -> Void))
(define (good-luck-helper-typed a b)
  (printf "~a, ~a!" a b))

Let’s see … the main changes are the places where “#lang typed-scheme” has been added, and where “(: good-luck-typed (String -> Void))” and “(: good-luck-helper-typed (String String -> Void))” have been inserted.

Let’s take a look at this piece of code.  The procedure “good-luck-typed” takes a parameter of type String, and returns nothing (i.e., it returns a value of type “Void”).  The procedure “good-luck-helper-typed” takes two parameters of type String, and also returns nothing (i.e., it also returns a value of type “Void”).

Let’s see what happens:

> (good-luck-typed "Benjamin")
Benjamin, Good Luck!
> (good-luck-typed "Nobody")
You are Nobody.
>

Yes, the results are identical.

Normally, I would start writing about the differences when errors arise, but I don’t have time today, so let’s do that next time.

Lastly, I became curious about whether currying (see http://en.wikipedia.org/wiki/Currying) was possible.  Let’s give it a try:

;; good-luck-curried.ss
;; Curried Typed Scheme version of good-luck.ss program to wish a person good luck
;; 
;; Copyright(C) October 20, 2008, at 17:44, 
;; by Benjamin L. Russell

#lang typed-scheme

(: good-luck-curried (String -> Void))
(define (good-luck-curried name)
  (if (string=? name "Nobody")
      (printf "You are ~a." name)
      ((good-luck-helper-curried name) "Good Luck")))

(: good-luck-helper-curried (String -> (String -> Void)))
(define ((good-luck-helper-curried a) b)
  (printf "~a, ~a!" a b))

Hmm … the main differences are the “(: good-luck-helper-curried (String -> (String -> Void)))” and “(define ((good-luck-helper-curried a) b).”  Indeed, our gourmet code looks curried.  ;-)  Still, I can’t help wondering why in “(: good-luck-helper-curried (String -> (String -> Void))),” the parentheses are folded to the right, while in “(define ((good-luck-helper-curried a) b),” they are folded to the left….

Moving on (there is no time left, so let’s worry about that next time), let’s see what happens:

> (good-luck-curried "Benjamin")
Benjamin, Good Luck!
> (good-luck-curried "Nobody")
You are Nobody.
>

Right, identical results again.

Let’s worry about the details next time.

How hot would you like your curried Typed Scheme?

Towers of Hanoi

Next, allow me to present a Haskell version of Towers of Hanoi:

-- hanoi_v1.1.hs
-- Haskell function to compute the Towers of Hanoi problem recursively
-- 
-- Usage: putStr (hanoi_shower (hanoi 1 2 3 n)), or 
--        putStr (hanoi_shower (hanoi 'a' 'b' 'c' n)), 
--        where the first three arguments of hanoi may be polymorphic types
--        (i.e., Chars, Ints, or any other suitable type), and n is the number
--        of discs to move from the source peg to the destination peg
-- 
-- Copyright(c) April 16, 2008, at 14:17, 
-- by Benjamin L. Russell
-- 
-- Update History:
-- 
-- Version 1.0.1
-- Changed program name in comments:
-- "Hanoi.hs" -> "hanoi.hs"
-- 
-- Version 1.0.2
-- Corrected copyright date: April 17 -> April 16
-- 
-- Update History:
-- 
-- Version 1.1
-- Added usage information.
-- October 17, 2008, at 14:45

hanoi :: a -> a -> a -> Int -> [(a, a)]
hanoi source using dest n
    | n == 0 = []
    | n == 1 = [(source, dest)]
    | otherwise = hanoi source dest using (n-1)
                  ++ hanoi source using dest 1
                         ++ hanoi using source dest (n-1)

hanoi_shower :: Show a => [(a, a)] -> String
hanoi_shower [] = ""
hanoi_shower ((a, b):moves) = unlines ["Move " ++ show a ++ " to "++ show b ++ "."] ++ hanoi_shower moves

To run the Haskell source code above, simply type:

putStr (hanoi_shower (hanoi 'a' 'b' 'c' 3))

You shall be rewarded with:

Move 'a' to 'c'.
Move 'a' to 'b'.
Move 'c' to 'b'.
Move 'a' to 'c'.
Move 'b' to 'a'.
Move 'b' to 'c'.
Move 'a' to 'c'.

Beautiful, isn’t it?

So much for now.  Until next time….

What is the taste of curried Haskell?

Towers of Hanoi

Ladies and Gentlemen!  Welcome to DekuDekuplex’s Blog, the Never Never Land of amateur functional programming theory!

What is the value of a process that doesn’t terminate?

Allow me to present my introductory Scheme procedure, Towers of Hanoi:

;; Towers of Hanoi, plt1.1
;; PLT-Scheme-specific Version 1.1 of Towers of Hanoi
;; 
;; Copyright(C) April 02, 2008, at 19:38, 
;; by Benjamin L. Russell

(define (hanoi n)
  (hanoi-helper 'A 'B 'C n))

(define (hanoi-helper source using destination n)
  (cond ((= n 1)
         (printf "Moving from disc ~a to ~a.\n" source destination))
        (else
         (hanoi-helper source destination using (- n 1))
         (hanoi-helper source using destination 1)
         (hanoi-helper using source destination (- n 1)))))

To run the Scheme source code above, simply type:

(hanoi 3)

You shall be rewarded with:

Moving from disc A to C.
Moving from disc A to B.
Moving from disc C to B.
Moving from disc A to C.
Moving from disc B to A.
Moving from disc B to C.
Moving from disc A to C.

Wonderful, isn’t it?

So much for now.  Until next time….

(lambda x.(x x))(lambda x.(x x))