I'm new to functional programming and I want to create my own structure/signature called Dictionary. So far I have this in file called dictionary-en.sml:
(* The signature DICTIONARY defines a type and a programming interface for
the dictionary data structure. The data structure allows us to store
data in the form of (key, value) pairs and to query the data using a key. *)
signature DICTIONARY =
sig
(* The structure has to implement a dictionary type. It defines key type,
which has to support equality checking, and a value type for the data
stored in the dictionary. *)
type (''key, 'value) dict
(* Creates an empty dictionary. *)
val empty: (''key, 'value) dict
(* Returns true if a key exists in the dictionary. *)
val exists: (''key, 'value) dict -> ''key -> bool
end
And I have this in file solution.sml:
structure Dictionary :> DICTIONARY =
struct
type (''key, 'value) dict = (''key * 'value) list
val empty = []
fun exists dict key =
case dict of
[] => false
| (k, _ )::rep => if k = key
then true
else exists rep key
end
But I don't how to use this. When I wrote in REPL:
- Dictionary.exists [(3,"c"), (5, "e"), (7, "g")] 3;
I got this error:
stdIn:1.2-3.7 Error: operator and operand do not agree [tycon mismatch]
operator domain: (''Z,'Y) Dictionary.dict
operand: ([int ty] * string) list
in expression:
Dictionary.exists ((3,"c") :: (5,"e") :: (<exp>,<exp>) :: nil)
Can someone please help me? I don't know what I did wrong.
In the function
fun exists dict key = case dict of [] => [] | (k, _ )::rep => if k = key then true else exists rep key
I spot two issues:
[]
in one place and true
in another.if P then true else Q
, write P orelse Q
.You're using :>
which means that the module is opaque, so you can only access the things specified in the signature. The internal list representation is not mentioned in the signature, so you can't refer to a dict as a list, even though you may know that that's how it's implemented. This is a feature.
I would probably call exists
for member
, since List.exists
is a higher-order predicate, e.g. List.exists (fn x => x > 5) [3, 6, 9]
. You could also deviate from any standard library naming and say containsKey
and containsValue
, or something like that.
Besides the insert
function that molbdnilo suggested, you may like to have a fromList
function.
Here's a refactored version (comments omitted for brevity, but I think your comments are good!):
signature DICTIONARY =
sig
type (''key, 'value) dict
val empty: (''key, 'value) dict
val member: ''key -> (''key, 'value) dict -> bool
val insert: (''key * 'value) -> (''key, 'value) dict -> (''key, 'value) dict
val fromList: (''key * 'value) list -> (''key, 'value) dict
end
structure Dictionary :> DICTIONARY =
struct
type (''key, 'value) dict = (''key * 'value) list
val empty = []
fun member key [] = false
| member key ((key2, _)::dict) =
key = key2 orelse member key dict
fun insert (key, value) [] = [(key, value)]
| insert (key, value) ((key2, value2)::dict) =
if key = key2
then (key, value) :: dict
else (key2, value2) :: insert (key, value) dict
fun fromList pairs = foldl (fn (pair, dict) => insert pair dict) empty pairs
end
But since you're building a dictionary module, there are two things you want to consider:
''key
to express that something can be ordered (Haskell generalises this as type classes, but Standard ML has only the special syntax ''key
), this is a good case for using functors, which is the name given to higher-order modules, aka parameterised modules.Here's an example signature, functor and structure that you can fill out:
signature ORD = sig
type t
val compare : t * t -> order
end
signature DICT = sig
type key
type 'value dict
val empty: 'value dict
val member: key -> 'value dict -> bool
val insert: key * 'value -> 'value dict -> 'value dict
val fromList: (key * 'value) list -> 'value dict
end
functor Dict (Ord : ORD) :> DICT = struct
type key = Ord.t
type 'value dict = (key * 'value) list
val empty = ...
fun member _ _ = raise Fail "not implemented"
fun insert _ _ = raise Fail "not implemented"
fun fromList _ = raise Fail "not implemented"
end
At this point you can change type 'value dict
into using a binary tree, and when you need to decide whether to go left or right in this binary tree, you can write:
case Ord.compare (key1, key2) of
LESS => ...
| EQUAL => ...
| GREATER => ...
And when you need a dictionary where the key is some particular orderable type, you can create a module using this functor:
structure IntDict = Dict(struct
type t = int
val compare = Int.compare
end)
structure StringDict = Dict(struct
type t = string
val compare = String.compare
end)
See also Standard ML functor examples for more examples.