Haskell, mapping String to Maybe a

Question

This question is already solved, it is a mapping from a String to a "Maybe a", with empty,insert,lookup functions as defined below, i'm unable to understand the solution.

The code:

type Map a = String -> Maybe a

empty :: Map a
empty = \x -> Nothing

insert :: (String, a) -> Map a -> Map a
insert (s, a) m = \x -> if x == s then Just a else m x

lookup :: String -> Map a -> Maybe a
lookup x m = m x

empty and lookup i think i understand.

insert however is puzzling to me,the lambda inside it i don't understand, how is x used in the equality when it is never taken as a parameter, x is from what i can see is a String, but it isn't given a value anywhere. what would be the resulting function from insert ("foo", 61) empty how would it be evaluated, and what does x represent?

also why would a line like this work and return "Just 61" lookup "foo" (insert ("foo", 61) empty)

Steven · Accepted Answer · 2022-11-06 01:50:36Z

When we say type Map a = String -> Maybe a, it is just a type alias, so Map a is identical to String -> Maybe a. Thus, you know that Map a is just a function type String -> Maybe a.

Therefore, when we say empty :: Map a, we want to define empty as a function from String to Maybe a. In this example, we have defined it as \x -> Nothing, which means empty is an empty map that maps every string x to Noting.

So we can look into insert :: (String, a) -> Map a -> Map a using the same method. The meaning for this function is to add one more mapping relation (i.e., (String, a) pair) to a given Map a, and the return value is a new Map a which contains the added pair. Therefore, by pattern matching insert (s, a) m, s is of type String, a is of type a, and m is of type Map a. Now we have to construct the result, which is of type Map a. Recall that Map a is just String -> Maybe a, so we have to construct a function here. To construct a function, we use the lambda expression here.

So by using lambda expression \x -> if x == s then Just a else m x, we are saying that this new Map a (function of type String -> Maybe a) takes a String x, and checks if it is equal to s (the string inserted this time). If it is not s, we use the old Map a (m) to check the remaining mapping.

The example could be calculated as:

  lookup "foo" (insert ("foo", 61) empty)
  {applying lookup}
= (insert ("foo", 61) empty) "foo"
  {applying insert}
= (\x -> if x == "foo" then Just 61 else (empty x)) "foo"
  {applying lambda expression, replacing x with "foo"}
= if "foo" == "foo" then Just 61 else (empty "foo")
  {applying if_then_else}
= Just 61

chepner · Accepted Answer · 2022-11-06 12:27:15Z

A Map a is a function; x is the parameter of that function. Looking up a key in a map just means calling the map on the key.

Consider the lookup of "foo" in a map than maps "foo" to 3.

lookup "foo" (insert ("foo", 3) empty)
   -- by the definition of lookup
   == (insert ("foo", 3) empty) "foo"
   -- by the definition of insert
   == (\x -> if x == "foo" then Just 3 else empty x) "foo"
   -- apply function to "foo"
   == if "foo" == "foo" then Just 3 else empty "foo"
   -- take the true branch
   == Just 3

Now consider the lookup of "bar" in the same map.

lookup "bar" (insert ("foo", 3) empty)
   == (insert ("foo", 3) empty) "bar"
   == (\x -> if x == "foo" then Just 3 else empty x) "bar"
   == if "bar" == "foo" then Just 3 else empty "bar"
   -- take the false branch
   == empty "bar"
   -- by definition of empty
   == (\x -> Nothing) "bar"
   -- apply function to "bar"
   == Nothing

Collectives™ on Stack Overflow

Haskell, mapping String to Maybe a

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related