www.jammni.de

Jacko1985

Gepostet:
13.12.2009 17:34

Abstrakter Datentyp Schlange in Haskell

Hallo alle zusammen, ich bin neu hier und wollte mal fragen ob mir jemand bei einer Aufgabe helfen kann.

Ich habe ide Aufgabe eine Schlange in Haskell zu implementieren, ich habe schon mehrere Arten erfolgreich implementiert aber diese bringt mich zur verzweiflung.
Vielleicht habe ich mich zu doll reingesteigert und sehe den Fehler nicht mehr.

Hier der Quelltext:

---adt Queue2; --------------------------------
-- File: queue2.hs	
module Queue2 where

-- is based on Character (predefined);
-- sorts
--     exports queue, element
--     uses char, int (predefined)

type Element = Char

-- abstract implementation
data Queue = Init | App( Queue, Element) | Underflow(Int) 
             deriving (Eq, Show)

-- public signature

empty    ::                     Queue
insert   :: (Queue, Element) -> Queue
remove   :: Queue            -> Queue
front    :: Queue            -> Element
errorel  ::                     Element
maxn     ::                     Int
number   :: Queue            -> Int
n        ::			Int

-- axioms
-- var q: queue; e: element n: Int

maxn = 3
n=(-1)

number( Init ) = 0
number( App( q, e) ) = number(q) + 1
number( Underflow(n) )   = -1


empty = Init

errorel = '-'

insert( q, e) =  if (e == errorel) then q
                 else if (number(q) <0) then Underflow(n+1)
			else if (number(q)>=maxn) then App(q,e)
				
				
				

remove( Init )       = Underflow(n)
remove( App( q, e) ) = if (q == Init) then Init else App( remove( q),e)
remove( Underflow(n) )  = Underflow(n-1)

front( Init )        = errorel
front( App( q, e) )  = if ( q == Init)  then e else front( q)
front( Underflow(n) )   = errorel



-- ende of specification ---------------------

Wir müssen diese Hausaufgaben in einem online System einreichen, wobei die Templates vorgeschrieben sind.
Das Problem habe ich mit der insert Methodem mir fällt keine letzte else Bedingung ein um das Programm zu vervollständigen.
Wobei wir so etwas wie Overflow nicht benutzen dürfen.
Das Online System hat bei meiner ersten Einreichung folgenden Test gemacht:

Your submission failed. Test case was: 'insert( insert( insert( insert( insert( insert( insert( empty, '1'), '2'), '3'), '4'), '5'), '6'), '7')'
Expected result: App (App (App (Init,'1'),'2'),'3')
Received result: App (App (App (App (App (App (App (Init,'1'),'2'),'3'),'4'),'5'),'6'),'7')

Ich hoffe das Problem habe ich verständlich genug erklärt.

Schonmal Danke für jede Art von Hilfe

Zum Seitenanfang

Siracusa

Gepostet:
13.12.2009 23:59

Hallo,

so wie ich das verstehe macht insert einfach gar nichts, falls maxn überschritten wurde, d.h. statt App (q,e) wird einfach q zurückgegeben. Außerdem würde ich dir empfehlen statt diesen verschachtelten if-then-elses lieber Guards zu verwenden, das ist übersichtlicher und einfacher erweiterbar.

Damit sähe dein insert in der aktuellen Version so aus:

insert( q, e)
  | e == errorel      = q
  | number(q) < 0     = Underflow(n+1)
  | number(q) >= maxn = App(q,e)  -- hier sollte nur q stehen
  | otherwise         = ... was auch immer ...

Viele Grüße,

Siracusa

Zum Seitenanfang

Haskell-Forum