home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 2 / DATAFILE_PDCD2.iso / utilities / _gofer / !Gofer / archives / Demos / gs / change < prev    next >
Text File  |  1993-02-12  |  660b  |  25 lines
  1. -- Let's represent coins by their integer values:
  2.  
  3. type Coin = Int
  4.  
  5. -- Denominations of coins in current use in the UK:
  6.  
  7. coins         :: [Coin]
  8. coins          = reverse (sort [1, 2, 5, 10, 20, 50, 100])
  9.  
  10. -- Find all possible (decreasing sequences) of change for given amount:
  11.  
  12. change        :: Int -> [[Coin]]
  13. change 0       = [[]]
  14. change amount  = [ c:cs | c<-coins, amount>=c, cs<-change (amount - c) ]
  15.  
  16. -- Find optimal change for given amount:
  17. -- intended semantics: change' = head . change
  18.  
  19. change'       :: Int -> [Coin]
  20. change' 0      = []
  21. change' amount = coin : change' (amount - coin)
  22.                  where coin = head [ c | c<-coins, c<=amount ]
  23.  
  24.  
  25.