basic-gps (empty) → 0.1.0.0

raw patch · 5 files changed

+92/−0 lines, 5 filesdep +base

Dependencies added: base

Files

• CHANGELOG.md +5/−0
• NOTES.md +18/−0
• README.md +9/−0
• basic-gps.cabal +25/−0
• src/GPS.hs +35/−0

@@ -0,0 +1,5 @@+# Revision history for basic-gps++## 0.1.0.0 -- YYYY-mm-dd++* First version. Released on an unsuspecting world.

@@ -0,0 +1,18 @@+It took me some time to make it. It looks very simple, but I've spend+a lot of time looking at different function types.++A little problem: I would like to write the types of functions in the code.+But there are problems with `ridid type` or `rigid variable` stuff.+So I decided not to write the types explicitly and it worked!+At first times, I wrote all the functions as global functions (I mean outside+the local scope of gps) and it worked. But with local functions I can create+closures and reference the list of operators in the gps argument instead of passing+it around and makind partial applications.++Types of functions in gps:+```haskell+achieveAll :: (Operator o g) => [g] -> [g] -> Maybe ([g], [o])+achieve :: (Operator o g) => ([g], [o]) -> g -> Maybe ([g], [o])+findApplicable :: [o]+tryApply :: o -> Maybe ([g], [o])+```

@@ -0,0 +1,9 @@+# Basic implementation of General Problem Solver algorithm++Key features:+- Written in Haskell in less than 50 LOC.+- Abstract. You can have different types for operations and goals.++Warning:+- It is not tested.+- It does not fix problems like clobbered sibling problem, or recursive subgoal problem, etc.

@@ -0,0 +1,25 @@+cabal-version:      2.4+name:               basic-gps+version:            0.1.0.0++synopsis: Basic implementation of General Problem Solver algorithm++description: Basic implementation of General Problem Solver algorithm. +             Untested, does not fix many problems. +             The algorithm is abstract: you can provide your own type of goals and operations.++license:            MIT+author:             InAnYan+maintainer:         ruslanpopov1512@gmail.com++category: AI++extra-source-files: CHANGELOG.md README.md NOTES.md++library+    exposed-modules:  GPS++    other-extensions: MultiParamTypeClasses +    build-depends:    base ^>=4.17.2.0+    hs-source-dirs:   src+    default-language: Haskell2010

@@ -0,0 +1,35 @@+{-# LANGUAGE MultiParamTypeClasses #-}++module GPS (Operator (..), gps) where++import Control.Monad (foldM)++-- | Class for representing the operators.+-- The property must hold: if doesAchieve o g then elem g (changeState s).+class (Eq g) => Operator o g where+  preconditions :: o -> [g]+  changeState :: o -> [g] -> [g]+  doesAchieve :: o -> g -> Bool++-- | The General Problem Solver algorithm.+gps :: (Operator o g) => [o] -> [g] -> [g] -> Maybe [o]+gps ops goals state = snd <$> achieveAll goals state+  where+    achieveAll state = foldM achieve (state, [])+      where+        achieve (state, acc) goal =+          if goal `elem` state+            then Just (state, acc)+            else firstJust tryApply findApplicable+          where+            findApplicable = filter (`doesAchieve` goal) ops++            tryApply o = do+              (state', actions) <- achieveAll state $ preconditions o+              return (state', acc ++ actions ++ [o])++firstJust :: (a -> Maybe b) -> [a] -> Maybe b+firstJust f (x : xs) = case f x of+  Just r -> Just r+  Nothing -> firstJust f xs+firstJust _ _ = Nothing