Hi,
profiling the attached program (a Haskell solution to an exercise from
the Prolog competition at JICSLP'98/Manchester by Heribert Sch�tz)
yields an invalid profile.hp:
---------------------------------------------------------------------
panne@marutea:~ > /usr/bin/hugs -d10000 compress.hs
[Hugs banner deleted]
Main> main
x(c(aab)3ccadad)2y
hp2ps: profile.hp, line 29: integer must follow identifier
---------------------------------------------------------------------
Line 29 in profile.hp is:
Undefined member: member: hen 1
This looks very strange, because the only string "Undefined member:"
is contained in Hugs' typechecker.
Setup:
uname -a:
Linux marutea 2.2.10 #3 Wed Sep 29 10:15:31 CEST 1999 i686 unknown
configure options:
--prefix=/usr --with-readline --with-preprocessor --enable-profiling
--enable-stack-dumps
Cheers,
Sven
--
Sven Panne Tel.: +49/89/2178-2235
LMU, Institut fuer Informatik FAX : +49/89/2178-2211
LFE Programmier- und Modellierungssprachen Oettingenstr. 67
mailto:[EMAIL PROTECTED] D-80538 Muenchen
http://www.informatik.uni-muenchen.de/~Sven.Panne
import Array
data ComprTree = Ch Char
| Sq ComprTree ComprTree
| Rp ComprTree Int
deriving (Show, Read)
-- Invariants:
-- - Rp has a numeric argument of at least 2 and at least 3 if its
-- subtree is a single Char.
-- - Rp is not directly nested.
-- - Sq is right-associative.
-- Optimal compressions obeying these (and more) invariants exist always.
ctToString ct = cts ct ""
where
cts (Ch c) = showChar c
cts (Sq t t') = cts t . cts t'
cts (Rp t n) = (case t of
Ch c -> showChar c
_ -> showChar '(' . cts t . showChar ')')
. shows n
expand ct = exp ct ""
where
exp (Ch c) = showChar c
exp (Sq t t') = exp t . exp t'
exp (Rp t n) = expRp n t
expRp 0 t = id
expRp n t = exp t . expRp (n-1) t
compress "" = ""
compress s = ctToString $ head $ compressions s
-- compressions is undefined for the empty string
compressions s = [ t
| n <- [0..lengthS]
, (t, p) <- enumerateCTs True True n 0
, atEnd p
]
where
lengthS = length s
atEnd p = p == lengthS
arrayS = array (0, lengthS-1) (zip [0..] s)
-- `enumerateCTs sq rp n p' enumerates the ComprTrees t with the following
-- properties:
-- - t obeys the invariants.
-- - t has a string representation of length n.
-- - t expands to a substring of s starting at position p.
-- The ComprTrees are paired with the end position of this string.
-- sq and rp say whether the top-level constructor may be `Sq' or `Rp', resp.
--
-- enumerateCTs is tabulated
enumerateCTs' _ _ 0 _ = []
enumerateCTs' _ _ 1 p = [ (Ch (arrayS!p), p+1)
| p < lengthS
]
enumerateCTs' sq rp n p = [ (Sq t t', p)
| sq
, p < lengthS
, nLeft <- [1..n-1]
, let nRight = n - nLeft
, (t , p) <- enumerateCTs False True nLeft p
, p < lengthS
, (t', p) <- enumerateCTs True True nRight p
]
++
if iOuter
then
[ (Rp t i, p)
| rp
, p < lengthS
----------------------------------------------
, i <- [2..lengthS-p]
, nParen <- [0, 2]
, let nSub = n - nParen - length (show i)
, nParen == (if nSub == 1 then 0 else 2)
, nSub > 0
, not (nSub == 1 && i == 2)
, (t , p) <- enumerateCTs True False nSub p
----------------------------------------------
, p <- checkString (expand (Rp t (i-1))) p
]
else
[ (Rp t i, p)
| rp
, p < lengthS
----------------------------------------------
, nSub <- [1..n-1]
, let nSubParen = nSub +
(if nSub == 1 then 0 else 2)
, n > nSubParen
, let p' = p
, (t , p) <- enumerateCTs True False nSub p
, i <- [if nSub == 1 then 3 else 2
..
(lengthS-p') `div` (p-p')]
, n == nSubParen + length (show i)
----------------------------------------------
, p <- checkString (expand (Rp t (i-1))) p
]
enumerateCTs sq rp n p = tab ! (sq, rp, n, p)
tab = array ((False, False, 0, 0),(True, True, lengthS, lengthS))
[ ((sq, rp, n, p), enumerateCTs' sq rp n p)
| sq <- [False .. True]
, rp <- [False .. True]
, n <- [0..lengthS]
, p <- [0..lengthS]
]
-- `checkstring xs p' checks whether s contains the substring xs at
-- position p. If so, a singleton list containing the end position of
-- the substring is returned. Otherwise the empty list is returned.
checkString "" p = [p]
checkString (x:xs) p = [ p
| p < lengthS
, x == arrayS!p
, p <- checkString xs (p+1)
]
-- iOuter chooses between two equivalent expressions enumerating Rp trees.
-- When true, the number of repetitions is chosen in an outer loop
-- and the repeated part is chosen in an inner loop. When false, the
-- loops are nested the other way round. (The latter seems to be slightly
-- more efficient.)
iOuter = False -- True
----------------------------------------------------------------------
testString = "xcaabaabaabccadadcaabaabaabccadady"
-- testString = "aaaaaabaabaabaab"
xxx = [ (ctToString c, expand c == testString)
| c <- compressions testString
]
-- main = do mapM_ print xxx
main = do putStrLn (compress testString)
