[Agda] Agda features/functionality that I can use

Sivaram Gowkanapalli sivaramreddy at hotmail.com
Wed Mar 30 07:37:43 CEST 2011


 Hello,

I am trying to write an agda program (mySolution.agda) for the "Escape From Zurg: An Exercise in Logic Programming" ( http://web.engr.oregonstate.edu/~erwig/zurg/ ).

This program lists all the possible options, after figuring out how to use the "<" (less-than) in agda.

Can you please let me know what agda functionality / features I can add to make this program better?

Thanks a lot


module mySolution where

open import Data.List --   using (List; []; _:_)
open import Data.Nat  --   using (ℕ)
open import Data.Tuple
open import Data.Bool
open import Data.Maybe
open import Function

data Toy : Set where
   Buzz   Woody   Rex   Hamm : Toy

time : Toy → ℕ
time Buzz   = 5
time Woody  = 10
time Rex    = 20
time Hamm   = 25

allToys : List Toy
allToys = Buzz ∷ Woody ∷ Rex ∷ Hamm ∷ []

LeftToys : Set
LeftToys = List Toy

RightToys : Set
RightToys = List Toy

FirstToy : Set
FirstToy = Toy
SecondToy : Set
SecondToy = Toy

mutual
   Backwards : Set
   Backwards = List (Maybe Tree)
   Forwards : Set
   Forwards = List (Maybe Tree)
   data Tree : Set where
      treeForward : FirstToy    → SecondToy
                    → LeftToys  → RightToys
                    → Backwards → Tree
      treeBackward : Toy
                     → LeftToys  → RightToys
                     → Forwards → Tree
{-
record Forward : Set where
   field firstToy  : Toy
         secondToy : Toy
         leftToys  : LeftToys
         rightToys : RightToys
         nextBackwardSteps : List BackwardTree
record Backward : Set where
   field toy       : Toy
         leftToys  : LeftToys
         rightToys : RightToys
         nextForwardSteps : List ForwardTree
mutual
   data Forward (FirstToy : Toy) (SecondToy : Toy)
                (LeftToys : Set) (RightToys : Set)
                (Backwards : List Tree)
            : Set where
      forward : FirstToy   → SecondToy
                → LeftToys → RightToys
                → Backwards
                → Forward FirstToy SecondToy
                          LeftToys RightToys
                          Backwards
   data Backward (Toy : Set)
                 (LeftToys : Set) (RightToys : Set)
            : Set where
      backward : Toy
                 → LeftToys → RightToys
                 → Forwards
                 → Backward Toy
                            LeftToys RightToys
                            Forwards
-}
{-
mutual
   Backwards : Set
   Backwards = List Backward
   Forwards : Set
   Forwards = List Forward
   data Forward (FirstToy : Toy) (SecondToy : Toy)
                (LeftToys : Set) (RightToys : Set)
                (Backwards : Set)
            : Set where
      forward : FirstToy   → SecondToy
                → LeftToys → RightToys
                → Backwards
                → Forward FirstToy SecondToy
                          LeftToys RightToys
                          Backwards
   data Backward (Toy : Set)
                 (LeftToys : Set) (RightToys : Set)
            : Set where
      backward : Toy
                 → LeftToys → RightToys
                 → Forwards
                 → Backward Toy
                            LeftToys RightToys
                            Forwards
-}

-- subsets of size k
combinationsOf : ℕ → List Toy → List (List Toy)
combinationsOf 0 _   = [ [] ]
combinationsOf _ []  = []
combinationsOf k (x ∷ xs) = map (_∷_ x) (combinationsOf (k ∸ 1) xs)
                            ++ combinationsOf k xs

toTuple : List Toy → Maybe (Toy × Toy)
toTuple (x ∷ y ∷ []) = just (tuple x y)
toTuple _ = nothing -- error "unknown combination"

_==_ : Toy → Toy → Bool
Buzz  == Buzz  = true
Woody == Woody = true
Rex   == Rex   = true
Hamm  == Hamm  = true
_     == _     = false

delete : Toy → List Toy → List Toy
delete toy toys = filter (λ a → not (a == toy)) toys

--fromJust : List (Maybe Toy) → List Toy
--fromJust xs = filter (λ a → not $ maybeToBool a) xs

mutual
   buildTree : LeftToys → RightToys → Maybe (Toy × Toy) → Maybe Tree
   buildTree (_ ∷ _ ∷ []) right (just (tuple firstToy secondToy))
      = just  (treeForward firstToy secondToy
                           -- toys on the left
                           []
                           -- toys on the right
                           (firstToy ∷ secondToy ∷ right)
                           -- child trees
                           [])
   buildTree left right (just (tuple firstToy secondToy))
      = just  (treeForward firstToy secondToy
                           -- toys on the left
                           lefttoys
                           -- toys on the right
                           righttoys
                           -- child trees
                           --(fromJust ∘ map (backwardMoves
                           (map (backwardMoves
                                             lefttoys
                                             righttoys)
                                     $ righttoys))
      where lefttoys  = delete firstToy ∘ delete secondToy $ left
            righttoys = firstToy ∷ secondToy ∷ right
   buildTree _ _ _ = nothing

   backwardMoves : LeftToys → RightToys → Toy → Maybe Tree
   backwardMoves left right backward
      = just  (treeBackward backward -- Backward
                            -- toys on the left
                            lefttoys
                            -- toys on the right
                            (delete backward right)
                            -- child trees
                            --(fromJust ∘ map (buildTree
                            (map (buildTree lefttoys righttoys
                                  ∘ toTuple)
                             ∘ combinationsOf 2
                             $ lefttoys))
      where lefttoys = backward ∷ left
            righttoys = (delete backward right)

allOptions : List (Maybe Tree)
allOptions = map (buildTree allToys [] ∘ toTuple)
                 ∘ combinationsOf 2 $ allToys

data Move : Set where
   moveF : FirstToy → SecondToy → Move
   moveB : Toy → Move

Choice : Set
Choice = List Move

mutual
   treesToChoices : List (Maybe Tree) → List Choice
   treesToChoices trees = concatMap treeToChoices trees

   treeToChoices : Maybe Tree → List Choice
   treeToChoices (just (treeForward x y [] _ []))
      = (((moveF x y) ∷ [] ) ∷ [])
   treeToChoices (just (treeForward x y _ _ nextSteps))
      = map (_∷_ (moveF x y)) $ treesToChoices nextSteps
   treeToChoices (just (treeBackward x _ _ nextSteps))
      = map (_∷_ (moveB x)) $ treesToChoices nextSteps
   treeToChoices (nothing) = (([]) ∷ [])

Cost : Set
Cost = ℕ

moveCost : Move → Cost
moveCost (moveF x y) = (time x) ⊔ (time y)
moveCost (moveB x) = time x

costOfChoice : Choice → (Cost × Choice)
costOfChoice choice = tuple (sum ∘ map moveCost $ choice) choice

costOfChoices : List Choice → List (Cost × Choice)
costOfChoices = map costOfChoice

lessThan : ℕ → ℕ → Bool
lessThan zero (suc y)    = true
lessThan (suc x) zero    = false
lessThan zero zero       = false
lessThan (suc x) (suc y) = lessThan x y

solution : List (Cost × Choice)
solution = filter (λ x → lessThan (fst x) 61)
           ∘ costOfChoices ∘ treesToChoices $ allOptions

{-
main : IO Unit
--main = putStrLn ∘ groom ∘ filter (λ (cost , _) → cost < 61)
main = putStrLn ∘ filter (λ < cost , _ > → cost < 61)
       ∘ costOfChoices ∘ treesToChoices $ allOptions
-}

 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20110330/c16c0739/attachment-0001.html


More information about the Agda mailing list