Path: utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!rpi!usc!sdd.hp.com!spool.mu.edu!uunet!mcsun!ukc!harrier.ukc.ac.uk!mr3
From: mr3@ukc.ac.uk (M.Rizzo)
Newsgroups: comp.sys.amiga.programmer
Subject: Functional Programming (Re: Good programmers and assembly language)
Message-ID: <7235@harrier.ukc.ac.uk>
Date: 7 Apr 91 20:48:18 GMT
References: <7214@harrier.ukc.ac.uk> <1523@tronsbox.xei.com>
Reply-To: mr3@ukc.ac.uk (M.Rizzo)
Organization: Computing Lab, University of Kent at Canterbury, UK.
Lines: 54

In article <1523@tronsbox.xei.com> dfrancis@tronsbox.xei.com (Dennis Heffernan) writes:
>In article <7214@harrier.ukc.ac.uk> mr3@ukc.ac.uk (M.Rizzo) writes:
>|In Miranda all you need is three lines:
>|
>|qsort :: [*] -> [*]
>|qsort [] = []
>|qsort (a:X) = qsort [b|b<-X; b<=a] ++ [a] ++ qsort [b|b<-X; b>a] 
>|

>	If learning a high-level language means putting up with gibberish like
>THAT, I think I'll switch to raw hex instead.

I think you've made a very hasty comment there. You are obviously put
off by the notation and confused by the totally different approach to
imperative programming languages such as C that most people are
used to.

But if you know how the quick sort algorithm works (you'll find this in
any decent algorithms book) you should be able to understand those
three lines if you think about it. They're almost a specification of
quick sort rather than an implementation !  Familiarity with set and
function notation in Mathematics is also very useful. Just to help you
along if you want to understand it better:

[*] denotes a list of items of the same arbitrary type
[]  denotes the empty list
[a] denotes the list containing only the item a
[b|condition; condition; ... ]  (called a List Comprehension) denotes
    the list of all b's which satisfy the ensuing conditions
++  is the operator which concatenates lists
h:T is used for pattern matching on lists. It will match any non-empty
    list, and place the first element of the list in h (head), the remaining
    list in T (tail) (In the above, a:X was used)

The third line is obviously using recursion. In my opinion this line
captures the essence of the quick sort algorithm very elegantly. Again
think of how many PASCAL or C statements you'd need to implement
quicksort (more the so for assembler).

I can assure you that languages such as Miranda, Hope and ML, do
provide significant advantages over traditional programming languages.
Their authors have analyzed the shortcomings of traditional languages
and written new ones to overcome them. A very good introduction to
such languages is given in "An Introduction to Functional Programming"
by Bird & Wadler (published by Prentice-Hall) for anyone who's interested.
Increasingly more universities are including functional programming in
their undergraduate courses - there are even opinions that a functional
language should replace Pascal as the traditional first language taught
at university.

Now all I want is a decent implementation of a functional language
for the Amiga! Did I hear anyone say they'd done a version of ML ?

Michael Rizzo