Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Author Message
Lazy

Posted: Tue Nov 14, 2006 3:13 pm   Post subject: [Haskell] Single Source All Paths

Hi all,

This is a little program I put together to practice Haskell. The specs can be found here: http://www.doc.ic.ac.uk/~ajf/Teaching/Haskell/sampleTest2.pdf, although I deviated a little from the assignment.

It's far from perfect. The instance declaration of Finite is incomplete, and I feel that some things can be done more elegantly. Time permiting, I'll try to rewrite it as a State monad, to carry around the graph.

 code: import List type Id = Int type Weight = Int type Edge  = ( Id, Id ) type Graph = [ ( Edge, Weight ) ] data Cost = Finite Weight | Infinity                 deriving ( Eq, Show ) edge     = fst cost     = snd fromId = ( fst . fst ) toId   = ( snd . fst ) instance Num Cost where         Infinity + _ = Infinity         _ + Infinity = Infinity         Finite a + Finite b = Finite ( a + b )         instance Ord Cost where         Infinity <= Infinity = True         Infinity <= Finite _ = False         Finite _ <= Infinity = True         Finite a <= Finite b = a <= b solve :: Id -> Graph -> [ ( Edge, Cost ) ] solve s graph = solve' s ( costs s graph ) [] where         solve' :: Id -> [ ( Edge, Cost ) ] -> [ ( Edge, Cost ) ] -> [ ( Edge, Cost ) ]         solve' _ [] n = n         solve' s c acc = solve' s c' acc' where                  minp  = cheapest c                  restp = delete minp c                  c' = map ( \ x -> relax x minp graph ) restp                  acc' = minp : acc   allIds :: Graph -> [ Id ] allIds graph = nub \$ concat [ ( [ fromId g ] ++ [ toId g ] ) | g <- graph ] lookUpCost :: Edge -> Graph -> Cost lookUpCost edge graph = let found = lookup edge graph in                   case found of                   Nothing -> Infinity                   Just a  -> Finite a costs :: Id -> Graph -> [ ( Edge , Cost ) ] costs s graph = [  ( ( s, x ), lookUpCost ( s, x ) graph ) | x <- allIds graph ] cheapest :: [ ( Edge, Cost ) ] -> ( Edge, Cost ) cheapest n = minimumBy ( \ x y -> compare ( cost x ) ( cost y ) ) n relax :: ( Edge, Cost ) -> ( Edge, Cost ) -> Graph -> ( Edge, Cost ) relax p minp graph = ( edge p, min ( cost p ) transit  ) where         transit = lookUpCost (fromId p, toId minp) graph + lookUpCost (toId minp, toId p) graph                        -- test data test :: Graph test= [ ( ( 0, 1 ), 1 ),         ( ( 0, 2 ), 3 ),         ( ( 0, 4 ), 6 ),         ( ( 1, 2 ), 1 ),         ( ( 1, 3 ), 3 ),         ( ( 2, 0 ), 1 ),         ( ( 2, 1 ), 2 ),         ( ( 2, 3 ), 1 ),         ( ( 3, 0 ), 3 ),         ( ( 3, 4 ), 2 ),         ( ( 4, 3 ), 1 ),         ( ( 5, 2 ), 9 ) ]

Tyr_God_Of_War

Posted: Sun Apr 24, 2011 9:48 am   Post subject: RE:[Haskell] Single Source All Paths

The pdf is gone, could you state the problem here?
apython1992

Posted: Sun Apr 24, 2011 3:26 pm   Post subject: RE:[Haskell] Single Source All Paths

Um...that post is about five years old.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 3 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: