tests/org.simantics.scl.compiler.tests/src/org/simantics/scl/compiler/tests/scl/Search.scl

   1 import "Prelude" hiding (findFirst)\r
   2 \r
   3 infinity = 1e9\r
   4 \r
   5 @inline\r
   6 findFirst :: (a -> <e> Maybe b) -> [a] -> <e> Maybe b\r
   7 findFirst f l = loop 0\r
   8   where\r
   9     len = length l\r
  10     loop i                         \r
  11         | i >= len  = Nothing\r
  12         | otherwise = match f (l!i) with\r
  13                         s @ (Just _) -> s\r
  14                         Nothing      -> loop (i+1)\r
  15 \r
  16 dfsFirst :: (a -> <e> Boolean) -> (a -> <e> [a]) -> [a] -> <e> (Maybe a)\r
  17 dfsFirst acceptable successors initial = tryAll initial\r
  18   where\r
  19     tryAll l = findFirst loop l\r
  20     loop p \r
  21         | acceptable p = Just p\r
  22         | otherwise    = tryAll (successors p)\r
  23 \r
  24 data Weighted a = Weighted a Double\r
  25 \r
  26 //type SearchAlgorithm e a =\r
  27 //    (a -> <e> Boolean) -> (a -> <e> [Weighted a]) -> [Weighted a] -> <e> Weighted (Maybe a)\r
  28     \r
  29 //dfs :: SearchAlgorithm e a\r
  30 dfs :: (a -> <e> Boolean) -> (a -> <e> [Weighted a]) -> [Weighted a] -> <e> Weighted (Maybe a)\r
  31 dfs acceptable successors initial = foldl loop (Weighted Nothing infinity) initial\r
  32   where\r
  33     loop best@(Weighted _ bestW) (Weighted p w)\r
  34         | w >= bestW   = best\r
  35         | acceptable p = Weighted (Just p) w\r
  36         | otherwise    = foldl loop best\r
  37                        $ map (\(Weighted p' w') -> Weighted p' (w+w'))\r
  38                        $ successors p\r
  39 \r
  40 /*\r
  41 bfs :: SearchAlgorithm e a\r
  42 \r
  43 aStar :: (a -> <e> Double) -> SearchAlgorithm e a\r
  44 */\r
  45 main = "Hello"\r
  46 --\r
  47 Hello