sort :: Ord a => [a] -> [a] sort [] = [] sort (x:xs) = insert x (sort xs)
insert :: Ord a => a -> [a] -> [a] insert x [] = [x] insert x (y:ys) = if x <= y then x : y : ys else y : insert x ys
main = putStrLn (sort "program")
$ hmake -hat Insort |
hat-trans Insort.hs |
Wrote TInsort.hs |
nhc98 -package hat -c -o TInsort.o TInsort.hs |
nhc98 -package hat -o Insort TInsort.o |
$ Insort |
agmoprr |
$ hat-trail Insort |
Output: ------------------------------------------------------- |
agmoprr\n |
Trail: ------ hat-trail 2.00 (:h for help, :q to quit) ------- |
return | add to the trail the parent expression of the current selection |
backspace | remove the last addition to the trail display |
arrow keys | select (a) parts of the output generated by different actions, or (b) subexpressions of expressions already on display |
:source | show the source expression of which the current selection is an instance |
:quit | finish this hat-trail session |
Trail: ----------------------- Insort.hs line: 10 col: 8 ------ |
<- putStrLn "agmoprr" |
Trail: ----------------------- Insort.hs line: 10 col: 1 ------ |
<-putStrLn "agmoprr" |
<-main |
backspace | (removes main), |
right-arrow | (selects putStrLn), |
right-arrow | (selects "agmoprr"), |
return | (requests parent expression) |
Trail: ----------------------- Insort.hs line: 7 col: 19 ----- |
<- putStrLn "agmoprr" |
<- insert 'p' "agmorr" | if False |
<- insert 'p' "agmorr" | if False |
<- insert 'r' "agmor" | if False |
<- insert 'o' "agmr" | if False |
<- insert 'g' "amr" | if False |
<- insert 'r' "am" | if False |
<- insert 'a' "m" | if True |
<- insert 'm' [] |
:quit |
$ hat-observe Insort |
hat-observe 2.00 (:h for help, :q to quit) |
hat-observe> |
:info | list the names of functions and other defined values that can be observed, with application counts |
:quit | finish this hat-observe session |
hat-observe> :info | ||||
19 <= | 21 insert | 1 main | 1 putStrLn | 1 sort |
hat-observe> sort | ||||
1 sort "program" = "agmoprr" | ||||
2 sort "rogram" = "agmorr" | ||||
3 sort "ogram" = "agmor" | ||||
4 sort "gram" = "agmr" | ||||
5 sort "ram" = "amr" | ||||
6 sort "am" = "am" | ||||
7 sort "m" = "m" | ||||
8 sort [] = [] |
hat-observe> <= |
1 'a' <= 'm' = True |
2 'r' <= 'a' = False |
3 'g' <= 'a' = False |
4 'o' <= 'a' = False |
5 'p' <= 'a' = False |
6 'r' <= 'm' = False |
7 'g' <= 'm' = True |
8 'o' <= 'g' = False |
9 'r' <= 'g' = False |
10 'p' <= 'g' = False |
--more--> |
--more--> n |
hat-observe> |
identifier pattern* [= pattern] [in identifier] |
_
as the only variable.
Some examples for the Insort computation:
hat-observe> insert 'g' _ |
1 insert 'g' "amr" = "agmr" |
2 insert 'g' "mr" = "gmr" |
hat-observe> insert _ _ = [_ ] |
1 insert 'm' [] = "m" |
2 insert 'r' [] = "r" |
hat-observe> sort in main |
1 sort "program" = "agmoprr" |
hat-observe> sort in sort |
1 sort "rogram" = "agmorr" |
2 sort "ogram" = "agmor" |
3 sort "gram" = "agmr" |
4 sort "ram" = "amr" |
5 sort "am" = "am" |
6 sort "m" = "m" |
7 sort [] = [] |
hat-observe> :quit |
In the following sections we shall apply the Hat tools to examine the faulty program, as if we didn't know in advance where the faults were.
sort :: Ord a => [a] -> [a] -- FAULT (1): missing equation for [] argument sort (x:xs) = insert x (sort xs)
insert :: Ord a => a -> [a] -> [a] insert x [] = [x] insert x (y:ys) = if x <= y -- FAULT (2): y missing from result then x : ys -- FAULT (3): recursive call is same else y : insert x (y:ys)
main = putStrLn (sort "program")
$ hmake -hat BadInsort |
... |
$ BadInsort |
No match in pattern. |
$ hat-trail BadInsort |
Error: -------------------------------------------------------- |
No match in pattern. |
Trail: ------------------- BadInsort.hs line: 3 col: 25 ------- |
<- sort [] |
<- sort "m" |
$ hat-observe BadInsort | |||
hat-observe 2.00 (:h for help, :q to quit) | |||
hat-observe> :info | |||
7+0 insert | 1 main | 1 putStrLn | 1+7 sort |
hat-observe> insert |
1 insert 'p' _|_ = _|_ |
2 insert 'r' _|_ = _|_ |
3 insert 'o' _|_ = _|_ |
4 insert 'g' _|_ = _|_ |
5 insert 'a' _|_ = _|_ |
6 insert 'm' _|_ = _|_
|
_|_
here indicates an undefined value. Reading the character
arguments vertically "program" seems to be misspelt: is there an observation
missing between 4 and 5? There are in fact two separate applications
insert 'r' _|_
= _|_
, but duplicate observations are not listed (by default).hat-observe> sort |
1 sort "program" = _|_ |
2 sort "rogram" = _|_ |
3 sort "ogram" = _|_ |
4 sort "gram" = _|_ |
5 sort "ram" = _|_ |
6 sort "am" = _|_ |
7 sort "m" = _|_ |
8 sort [] = _|_
|
_|_
results
already observed8.
Observation 8 is the application that does not reduce.hat-observe> putStrLn |
1 putStrLn _|_ = {IO} |
hat-observe> main |
1 main = {IO} |
sort [] = [] |
$ BadInsort |
Program interrupted. (^C) |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa$ |
Error: -------------------------------------------------------- |
Program interrupted. (^C) |
Output: ------------------------------------------------------- |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
Output: ------------------------------------------------------- |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
Trail: ----------------- BadInsort.hs line: 7 col: 19 -------- |
<- putStrLn "aaaaaaaa..." |
<- insert 'p' ('a':_) | if False |
_
in the list argument to insert indicates an expression
that was never evaluated.
_
) | if False gives several
important clues.
It tells us that in the else-branch of the recursive case in the
definition of insert the argument's head (here 'a') is duplicated
endlessly to generate the result without ever demanding the argument's
tail (shown only as _
). This should be enough explanation to discover
the fault if we didn't already know it.hat-observe> :info | ||||
78 <= | 1+83 insert | 1 main | 1 putStrLn | 8 sort |
hat-observe> sort |
1 sort "program" = "aaaaaaaaaa..." |
2 sort "rogram" = 'a':_ |
3 sort "ogram" = 'a':_ |
4 sort "gram" = 'a':_ |
5 sort "ram" = 'a':_ |
6 sort "am" = "a" |
7 sort "m" = "m" |
8 sort [] = [] |
hat-observe> insert |
1 insert 'p' ('a':_ ) = "aaaaaaaaaa..." |
2 insert 'r' ('a':_ ) = 'a':_ |
3 insert 'o' ('a':_ ) = 'a':_ |
4 insert 'g' ('a':_ ) = 'a':_ |
5 insert 'a' "m" = "a" |
6 insert 'm' [] = "m" |
searching ... (^C to interrupt) |
{Interrupted} |
_
)
in progress, each with results evaluated to a different extent.$ BadInsort |
agop |
hat-observe> insert _ _ = "agop" |
1 insert 'p' "agor" = "agop" |
hat-observe> insert 'p' _ in insert |
1 insert 'p' "gor" = "gop" |
2 insert 'p' "or" = "op" |
3 insert 'p' "r" = "p" |
Output: ------------------------------------------------------ |
agop\n |
Trail: ----------------- BadInsort.hs line: 10 col: 26 ------- |
<- putStrLn "agop" |
<- insert 'p' "agor" | if False |
This document was translated from LATEX by HEVEA.