projects
/
lambda.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
links on do-notation to translation
[lambda.git]
/
hints
/
assignment_7_hint_6.mdwn
diff --git
a/hints/assignment_7_hint_6.mdwn
b/hints/assignment_7_hint_6.mdwn
index
38f6c2e
..
fd8f55d
100644
(file)
--- a/
hints/assignment_7_hint_6.mdwn
+++ b/
hints/assignment_7_hint_6.mdwn
@@
-19,35
+19,37
@@
let new_dpm = fun (r, h) ->
(* if one_dpm isn't already false at (r, h),
we want to check its behavior when updated with phi
let new_dpm = fun (r, h) ->
(* if one_dpm isn't already false at (r, h),
we want to check its behavior when updated with phi
-
bind_set (unit_se
t one_dpm) phi === phi one_dpm; do you remember why? *)
- let (truth_value,
_, _
) = one_dpm (r, h)
+
set_bind (set_uni
t one_dpm) phi === phi one_dpm; do you remember why? *)
+ let (truth_value,
r', h'
) = one_dpm (r, h)
in let truth_value' = truth_value && (truths (phi one_dpm) (r, h) = [])
(* new_dpm must return a (bool, r, h) *)
in let truth_value' = truth_value && (truths (phi one_dpm) (r, h) = [])
(* new_dpm must return a (bool, r, h) *)
- in (truth_value', r
, h
)
- in
unit_se
t new_dpm;;
+ in (truth_value', r
', h'
)
+ in
set_uni
t new_dpm;;
- **
Note: Simon pointed out a subtle error in this code, which we will look into fixing. At the moment, the subtle error is still there.**
+ **
Thanks to Simon Charlow** for catching a subtle error in previous versions of this function. Fixed 1 Dec.
* Representing \[[and φ ψ]] is simple:
let and_op (phi : clause) (psi : clause) : clause =
* Representing \[[and φ ψ]] is simple:
let and_op (phi : clause) (psi : clause) : clause =
- fun one_dpm ->
bind_set
(phi one_dpm) psi;;
+ fun one_dpm ->
set_bind
(phi one_dpm) psi;;
(* now u >>= and_op phi psi === u >>= phi >>= psi; do you remember why? *)
* Here are `or` and `if`:
(* now u >>= and_op phi psi === u >>= phi >>= psi; do you remember why? *)
* Here are `or` and `if`:
+ (These probably still manifest the bug Simon spotted.)
+
let or_op (phi : clause) (psi : clause) =
let or_op (phi : clause) (psi : clause) =
- fun one_dpm ->
unit_se
t (
+ fun one_dpm ->
set_uni
t (
fun (r, h) ->
let truth_value' = (
truths (phi one_dpm) (r, h) <> [] ||
fun (r, h) ->
let truth_value' = (
truths (phi one_dpm) (r, h) <> [] ||
- truths (
bind_set
(negate_op phi one_dpm) psi) (r, h) <> []
+ truths (
set_bind
(negate_op phi one_dpm) psi) (r, h) <> []
) in (truth_value', r, h))
let if_op (phi : clause) (psi : clause) : clause =
) in (truth_value', r, h))
let if_op (phi : clause) (psi : clause) : clause =
- fun one_dpm ->
unit_se
t (
+ fun one_dpm ->
set_uni
t (
fun (r, h) ->
let truth_value' = List.for_all (fun one_dpm ->
let (truth_value, _, _) = one_dpm (r, h)
fun (r, h) ->
let truth_value' = List.for_all (fun one_dpm ->
let (truth_value, _, _) = one_dpm (r, h)
@@
-63,17
+65,17
@@
type assignment = char -> int;;
type store = entity list;;
type 'a dpm = assignment * store -> 'a * assignment * store;;
type assignment = char -> int;;
type store = entity list;;
type 'a dpm = assignment * store -> 'a * assignment * store;;
- let
unit_dpm
(x : 'a) : 'a dpm = fun (r, h) -> (x, r, h);;
- let
bind_dpm
(u: 'a dpm) (f : 'a -> 'b dpm) : 'b dpm =
+ let
dpm_unit
(x : 'a) : 'a dpm = fun (r, h) -> (x, r, h);;
+ let
dpm_bind
(u: 'a dpm) (f : 'a -> 'b dpm) : 'b dpm =
fun (r, h) ->
let (a, r', h') = u (r, h)
in let u' = f a
in u' (r', h')
type 'a set = 'a list;;
fun (r, h) ->
let (a, r', h') = u (r, h)
in let u' = f a
in u' (r', h')
type 'a set = 'a list;;
- let
empty_set
: 'a set = [];;
- let
unit_se
t (x : 'a) : 'a set = [x];;
- let
bind_set
(u : 'a set) (f : 'a -> 'b set) : 'b set =
+ let
set_empty
: 'a set = [];;
+ let
set_uni
t (x : 'a) : 'a set = [x];;
+ let
set_bind
(u : 'a set) (f : 'a -> 'b set) : 'b set =
List.concat (List.map f u);;
type clause = bool dpm -> bool dpm set;;
List.concat (List.map f u);;
type clause = bool dpm -> bool dpm set;;
@@
-91,18
+93,18
@@
fun entity_dpm ->
let eliminator = fun truth_value ->
if truth_value = false
fun entity_dpm ->
let eliminator = fun truth_value ->
if truth_value = false
- then
unit_dpm
false
- else
bind_dpm entity_dpm (fun e -> unit_dpm
(f e))
- in fun one_dpm ->
unit_set (bind_dpm
one_dpm eliminator);;
+ then
dpm_unit
false
+ else
dpm_bind entity_dpm (fun e -> dpm_unit
(f e))
+ in fun one_dpm ->
set_unit (dpm_bind
one_dpm eliminator);;
(* doing the same thing for binary predicates *)
let lift_predicate2 (f : entity -> entity -> bool) : entity dpm -> entity dpm -> clause =
fun entity1_dpm entity2_dpm ->
let eliminator = fun truth_value ->
if truth_value = false
(* doing the same thing for binary predicates *)
let lift_predicate2 (f : entity -> entity -> bool) : entity dpm -> entity dpm -> clause =
fun entity1_dpm entity2_dpm ->
let eliminator = fun truth_value ->
if truth_value = false
- then
unit_dpm
false
- else
bind_dpm entity1_dpm (fun e1 -> bind_dpm entity2_dpm (fun e2 -> unit_dpm
(f e1 e2)))
- in fun one_dpm ->
unit_set (bind_dpm
one_dpm eliminator);;
+ then
dpm_unit
false
+ else
dpm_bind entity1_dpm (fun e1 -> dpm_bind entity2_dpm (fun e2 -> dpm_unit
(f e1 e2)))
+ in fun one_dpm ->
set_unit (dpm_bind
one_dpm eliminator);;
let new_peg_and_assign (var_to_bind : char) (d : entity) : bool -> bool dpm =
fun truth_value ->
let new_peg_and_assign (var_to_bind : char) (d : entity) : bool -> bool dpm =
fun truth_value ->
@@
-116,7
+118,7
@@
(* from hint 5 *)
let exists var : clause =
let extend one_dpm (d : entity) =
(* from hint 5 *)
let exists var : clause =
let extend one_dpm (d : entity) =
-
bind_dpm
one_dpm (new_peg_and_assign var d)
+
dpm_bind
one_dpm (new_peg_and_assign var d)
in fun one_dpm -> List.map (fun d -> extend one_dpm d) domain
(* include negate_op, and_op, or_op, and if_op as above *)
in fun one_dpm -> List.map (fun d -> extend one_dpm d) domain
(* include negate_op, and_op, or_op, and if_op as above *)
@@
-124,7
+126,7
@@
* More:
(* some handy utilities *)
* More:
(* some handy utilities *)
- let (>>=) =
bind_set
;;
+ let (>>=) =
set_bind
;;
let getx = get 'x';;
let gety = get 'y';;
let initial_set = [fun (r,h) -> (true,r,h)];;
let getx = get 'x';;
let gety = get 'y';;
let initial_set = [fun (r,h) -> (true,r,h)];;