Prospering With Miranda

A LaTeX document that doubles as a Miranda literate script.

Iain Sinclair, Ryan Shelswell ed.

Type Notation

In Miranda, every constant, variable and function has a type. Unlike other languages, Miranda is usually able to work out the type of an expression without a declaration. However, the Miranda programmer will often declare the expression's type if it is ambiguous or complex. For example, to say ``the variable population is of type num'':

>population::num

The num type encompasses all numeric types -- there is no division into int, real or float. Note that thickness is of type num, but has no explicit type declaration:

>population=17041203
>thickness=0.2321

Truth values are of bool type, and are either True or False. A single character or letter is of char type. Any ASCII character can be represented with a backslash followed by the corresponding decimal number, using C-like conventions.

>absolute=True
>arafura='c'
>escape='\032'
>crg_return='\013'
>crg_return'='\n'
>tab='\t'
>backslash='\\'
>quote='\''

These primitive types (num, bool, char) are used with versatile data types (lists, tuples, functions). Miranda permits the creation of new, user-defined algebraic and abstract data types, such as trees, queues or tables.

A list is a sequence of any type (including other list types). They can be thought of as unbounded arrays which may contain no elements, some elements, or an infinite number of elements. Strings are represented as lists of char, and can be written within "" quotes instead of individual characters within brackets.

>truth_values::[bool]
>truth_values= [True,False,True,True]

>num_lists::[[num]]
>num_lists= [[],[22,67],[80]]

>blossom::[char]
>blossom=['w','a','t','t','l','e']
>blossom'="wattle"

A tuple groups zero or more (possibly differing) types, rather like a record in Pascal or a struct in C.

>certificate::([char],num)
>certificate= ("Glen O'Fathead",1967)

Function types describe the type of a function's arguments, and the type that a function returns. There are no procedure- or void-style functions in Miranda a function must ``take something'', and it must ``return something''. (However, a variable or a constant could be considered a function without arguments or parameters.)

For example, apply'fn takes two arguments: the name of a function (such as tan or abs) and a number. It returns a number -- the result of applying the named function to the second argument.

>apply'fn::(num->num)->num ->num
>apply'fn f x=(f x)

Note that Miranda doesn't show the brackets of right-associative functions, so that would be printed as (*->*)->*->*.

There are also polymorphic types, which represent generic or unknown types. Polymorphic types `match' other types. In Miranda, each polymorphic type is written *, **, ***, ****... corresponding to , , , ...

The symbol (bottom) is written in Miranda as undef .

The in-built function show is a polymorphic function which converts its argument to a string. Its type, , is the same as our example, ignore:

>ignore:: *->[char]
>ignore x= "So what?"

>|| predicate that checks if its argument is in error
>defined:: *->bool
>defined x= (x=undef)

List Manipulation

Lists can be constructed with extremely compact and elegant expressions. For example, a function which returns a list of even square numbers up to a specified limit:

>evsquares::num->[num]
>evsquares limit = [n*n | n<-[1..limit]; n mod 2=0 ]

Table B.1: List element-selection functions

>insect=       hd "bear"
>bird=         tl "beagle"
>complete xs=  init xs ++ [last xs]

>|| substitute position <x> in <xs> with <e>
>subst::num->[*]->*->[*]
>subst x xs e= take (x-1) xs ++ [e] ++ drop (#xs-x-1) xs

To return the longest initial segment of a list whose elements satisfy some predicate, use takewhile predicate. Similarly, dropwhile predicate is its complement; it returns the rest of the list, with the initial segment of elements satisfying predicate removed.

The order of elements in a finite list can be reversed using reverse.

>|| predicate to test whether xs reads the same forwards or backwards
>palindrome::[*]->bool
>palindrome xs=(reverse xs=xs)

With the zip family of functions, one can `zip' the elements of n lists together to return a list of n-tuples. The foldl and foldr functions are also important; they `fold up' a list from the left or right, performing cumulative operations.

>enumerate::[*]->[(num,*)]
>enumerate xs=zip2 [1..] xs

>bintodec::[num]->num
>bintodec xs=foldl (treatdigit) 0 xs
>            where treatdigit x d=(2*d)+x

The where clause should be aligned just past the = sign, to prevent the Miranda compiler from complaining about ``OFFSIDE errors''.

Table B.2: List operators

>prepend'3'nines::[num]->[num]
>prepend'3'nines xs=9:[9,9]++xs
 
>third'element:: [*]->*
>third'element xs=xs!2

You will have noticed by now that the first element in a list is denoted by ! 0.

A function can be applied (mapped) to each element of a list using map. It returns a list of the same length as its second argument. Along the same lines, filter removes the elements of a list which do not satisfy a given predicate.

>capitalise::[char]->[char]
>capitalise xs=map toupr xs
>              where toupr letter=decode ((code letter)-delta),
>                                         'a'<=letter<='z'
>                                =letter,  otherwise
>                                 where delta=code 'a'-code 'A'

>sarcophagus=filter (>'r') "grabbing red nuts here"

New Types

Miranda provides ample facilities for creating new types.

The new type, like Miranda's primitive types, is `constructed' by specifying the states it can assume. These states are called constructors, and must begin with capital letters. For example, the bool type is comprised of the True or False constructors.

>bloom::= Azalea | Waratah | Bottlebrush | Gladiola |
>         Sundew | Rose

The order of enumeration in this algebraic data type is significant. Gladiola is defined to be `less than' Bottlebrush, in the same way that Miranda defines False to be `less than' True.

Composite types are those whose value/state is dependent on other types. For example, a composite type which allows the labelling of individual blooms could be defined, so that: ``the type tag consists of a labelled bloom and a string, or a bloom with no label''.

>tag::= Label bloom [char] | Nolabel bloom

>flower::tag
>offering::tag

>flower= Nolabel Azalea
>offering= Label Rose "This one was white. I gave it to her with a \
>    box of crayons, because I didn't know what colour she wanted..."

Recursion is permitted in composite types. This allows us to specify more complex data types, such as trees. In this example, a list-like type is constructed from a terminator (Stop) and a recursive constructor (Tally):

>garden::= Stop | Tally num bloom (owner)

The Stop terminator is like a binary tree's Root or a list's Nil -- it `terminates' any number of Tally definitions.

>windowbox::garden
>windowbox=(Tally 3 Waratah (Tally 8 Sundew (Tally 1 Rose (Stop))))

The new type is just like any other type -- it can be referred to in functions, played around with in the interpreter, etc. A simple function which tallies the number of blooms might look like:

>count_blooms::bloom->num
>count_blooms (Tally)=0
>count_blooms (Tally amount plant rest)=amount + count_blooms rest

>plant::bloom
>amount::num

Note the presence of the plant and amount placeholder types. These are like algebraic types with no constructors; they allow us to ``hold a place during program development'', so that we can provide a more specific type definition later.

Implementing Abstract Data Types

Like other recently-developed languages (eg. Ada, Eiffel), Miranda has a linguistic facility for implementing abstract data types-- the abstype. Programmers can choose from a fair range of data representations.

Examples of ADTs include the stack (a well-worn example) and the (lookup) table.

Generally, the specification for ADTs consists of the type name, a list of the operations that can be performed on the type, and an optional spec of the range of values that the type may assume. In Miranda, it is possible to write ADT specifications (behaviour constraints) and implementations (a working data representation).

>|| Implementation for a coordinate type. Permissible operations:
>|| create, delta, zero, swap, show.
 
>abstype coord
>with
>	create:: num->num->coord
>	deltacoord:: num->num->coord->coord
>	zerocoord:: coord->coord
>	swapcoord:: coord->coord
>	showcoord:: coord->[char]
 
>|| coordinate implemented using a tuple
>coord==(num,num)
>a::num
>b::num
 
>|| bring a coord into existence
>create a b=(a,b)
 
>|| change a coord by some x & y "delta" (increment/decrement)
>deltacoord x y (a,b)=(a+x,y+b)
 
>|| set a coord to the origin
>zerocoord (a,b)=(0,0)
 
>|| swap a coord's position - swap X and Y values
>swapcoord (a,b)=(b,a)
 
>|| string representation of a coord
>showcoord (a,b)="X    Y"++"\n"++
>                ljustify 3 (show a)++rjustify 3 (show b)

Note well that there is no way to see/display the state of an ADT unless the programmer specifically writes a function to do so. (Otherwise, the interpreter just displays an abstract ob.) In Miranda, this function must begin with show so that the compiler knows which function to use when the object has to be converted to a print representation.