Declaratieve Talen/Oplossing Dijkstra Alternatief (Haskell)

Alternatieve oplossing (geeft pad en afstand terug)

import List

data Afstand = Afst Int | Inf deriving Show

instance Eq Afstand where
	(Afst x) == (Afst y) = x == y
	Inf == _ = False
	_ == Inf = False
	
instance Ord Afstand where
	(Afst x) <= (Afst y) = x <= y
	Inf <= _ = False
	_ <= Inf = True
	
------------------------------------------------------------------------
	
dijkstra :: String -> String -> (Afstand, String)
dijkstra s e = 
	let
		allknopen = knopen
		init = (Afst 0, s, s) : [(Inf, kn, "") | kn <- allknopen, kn /= s]
		tabel = dijkstra2 e allknopen init
		--
		distance = getdistance e tabel
		path = findpath s e tabel
	in	
		(distance, path)
		
------------------------------------------------------------------------
--- Dijkstra algoritme: stel tabel op (Afstand, Punt, KortsteAfstandPunt)

dijkstra2 :: String -> [String] -> [(Afstand, String, String)] -> [(Afstand, String, String)]
dijkstra2 endknoop remknopen tabel =
	let
		klknoop@(_, k, _) = zoek_kleinste remknopen tabel
		newremknopen = delete k remknopen
		newtable = updatetabel newremknopen klknoop tabel
	in
		if (k == endknoop)
		then
			newtable
		else
			dijkstra2 endknoop newremknopen newtable
		
updatetabel :: [String] -> (Afstand, String, String) -> [(Afstand, String, String)] -> [(Afstand, String, String)]
updatetabel _ _ [] = []
updatetabel remknopen klknoop@(dmin, kmin, _) (currknoop@(dcurr, kcurr, _) : xs) =
	if (elem kcurr remknopen)
	then
		let
			newcurrknoop = getnewdist klknoop currknoop
		in
			newcurrknoop : updatetabel remknopen klknoop xs
	else
		currknoop : updatetabel remknopen klknoop xs
	
getnewdist :: (Afstand, String, String) -> (Afstand, String, String) -> (Afstand, String, String)
getnewdist (dmin, kmin, kminorig) orig@(dcurr, kcurr, kcurrorig) =
	let
		dnew = plusafstand dmin (boog kmin kcurr)
		--dnew = min dcurr drol
	in
		if dcurr < dnew
		then
			orig --(dcurr, kcurr, kcurrorig)
		else
			(dnew, kcurr, kmin)

plusafstand :: Afstand -> Afstand -> Afstand
plusafstand Inf _ = Inf
plusafstand _ Inf = Inf
plusafstand (Afst x) (Afst y) = Afst (x + y)

zoek_kleinste :: [String] -> [(Afstand, String, String)] -> (Afstand, String, String)
zoek_kleinste remknopen [curr@(_, k, _)] =
	if (elem k remknopen)
	then
		curr
	else
		(Inf, "Error", "")
zoek_kleinste remknopen (newcandid@(d0, k0, _) : xs) = 
	let
		smallest@(d1, k1, _) = zoek_kleinste remknopen xs
	in
		if (d0 < d1 && (elem k0 remknopen))
		then
			newcandid
		else
			smallest

------------------------------------------------------------------------
--- Pad bepalen

findpath :: String -> String -> [(Afstand, String, String)] -> String
findpath s e table 	| s == e = s
					| otherwise = 
						let
							nextkey = getnext table e
						in
							(findpath s nextkey table) ++ e
						

getnext :: [(Afstand, String, String)] -> String -> String
getnext ((_, key0, nextkey) : xs) key1	| key0 == key1 = nextkey
										| otherwise = getnext xs key1

------------------------------------------------------------------------
--- Afstand opzoeken in tabel
getdistance :: String -> [(Afstand, String, String)] -> Afstand
getdistance key1 ((dist, key0, _) : xs)	| key0 == key1 = dist
										| otherwise = getdistance key1 xs
		

------------------------------------------------------------------------
-- Geimproviseerde gegevens

boog :: String -> String -> Afstand
boog s e	| dist s e < Inf	= dist s e
			| otherwise			= dist e s

dist :: String -> String -> Afstand
dist "a" "b" = Afst 1
dist "a" "c" = Afst 2
dist "a" "d" = Afst 10
dist "b" "c" = Afst 5
dist "c" "d" = Afst 1
dist _ _ = Inf

knopen :: [String]
knopen = ["a", "b", "c", "d"]