Tools

True Randomness

i
-- Read n bytes of OS entropy and combine them into a single Nat
def randomBytes (n : USize) : IO Nat := do
  let bytes  IO.getRandomBytes n
  return bytes.toList.foldl (fun acc b => acc * 256 + b.toNat) 0

-- Return a Nat sampled uniformly from [lo, hi] (both inclusive)
def randomInRange (lo hi : Nat) : IO Nat := do
  let raw  randomBytes 4  -- 4 bytes = 32 bits of entropy
  return lo + raw % (hi - lo + 1)
i
-- Pure helper exposed for testing: maps a raw value to the range [lo, hi]
def mapToRange (lo hi raw : Nat) : Nat := lo + raw % (hi - lo + 1)

-- raw = 0 always maps to lo
#guard mapToRange 1 6 0 == 1
-- raw = hi - lo always maps to hi (the top is reachable)
#guard mapToRange 0 5 5 == 5
-- result is always at most hi
#guard mapToRange 0 9 999  9
-- result is always at least lo
#guard mapToRange 3 7 0  3
i
def main : IO Unit := do
  let roll  randomInRange 1 6
  IO.println s!"dice roll: {roll}"
  let pick  randomInRange 0 2
  IO.println s!"random colour: {(["red", "green", "blue"])[pick]!}"
  -- sample a few values to show the range
  let samples  List.range 5 |>.mapM (fun _ => randomInRange 10 99)
  IO.println s!"five samples in [10, 99]: {samples}"
i
dice roll: 1
random colour: blue
five samples in [10, 99]: [96, 93, 40, 56, 71]

Building and Parsing JSON

i
-- Construct a JSON object with named fields
def makePerson (name : String) (age : Nat) : Json :=
  Json.mkObj [("name", Json.str name), ("age", Json.num age)]

-- Construct a JSON array of numbers
def makeScores (xs : List Nat) : Json :=
  Json.arr (xs.map (Json.num  JsonNumber.fromNat)).toArray
i
-- Extract a String field; return none if absent or the wrong type
def getStr (j : Json) (key : String) : Option String :=
  match j.getObjValAs? String key with
  | .ok s    => some s
  | .error _ => none

-- Extract a Nat field; return none if absent or the wrong type
def getNat (j : Json) (key : String) : Option Nat :=
  match j.getObjValAs? Nat key with
  | .ok n    => some n
  | .error _ => none
i
-- build: fields are accessible after construction
#guard
  let p := makePerson "Ada" 36
  getStr p "name" == some "Ada" && getNat p "age" == some 36

-- build: missing field returns none
#guard (getNat (makePerson "Euler" 76) "score").isNone

-- array: length matches the source list
#guard
  match makeScores [10, 20, 30] with
  | Json.arr vs => vs.size == 3
  | _           => false

-- parse: round-trip through a JSON string
#guard
  match Json.parse "{\"name\": \"Grace\", \"age\": 107}" with
  | .error _ => false
  | .ok v    => getStr v "name" == some "Grace" && getNat v "age" == some 107

-- parse: malformed input signals an error
#guard !(Json.parse "not json").isOk
i
def main : IO Unit := do
  -- Build and print
  let p := makePerson "Lean" 4
  IO.println s!"person: {p}"
  IO.println s!"scores: {makeScores [85, 92, 78]}"
  -- Parse a JSON string and extract fields
  match Json.parse "{\"name\": \"Turing\", \"age\": 41}" with
  | .error e => IO.println s!"parse error: {e}"
  | .ok v    =>
    let name := (getStr v "name").getD "?"
    let age  := (getNat v "age").getD  0
    IO.println s!"parsed: {name}, age {age}"
i
person: {"name": "Lean", "age": 4}
scores: [85, 92, 78]
parsed: Turing, age 41

Fetching Data with HTTP

i
-- Fetch the body of a plain-HTTP URL using Lean's native HTTP library.
-- Returns none if the URL is malformed, DNS lookup fails,
-- or the TCP connection is refused.  HTTPS is not supported.
def fetchUrl (url : String) : IO (Option String) := do
  try
    -- parse the URL and extract host and port
    let some uri := URI.parse? url | return none
    let some auth := uri.authority | return none
    let host := toString auth.host
    let port : UInt16 := match auth.port with
      | .value p => p
      | _        => URI.Scheme.defaultPort uri.scheme
    -- resolve hostname to one or more IP addresses
    let addrs  (DNS.getAddrInfo host "http").block
    let some ip := addrs[0]? | return none
    let sockAddr : SocketAddress := match ip with
      | .v4 a => .v4 { addr := a, port := port }
      | .v6 a => .v6 { addr := a, port := port }
    -- build the request target (path + query string)
    let pathStr :=
      let p := toString uri.path
      let q := toString uri.query
      if p.isEmpty then "/" ++ q else p ++ q
    let target := RequestTarget.originForm! pathStr
    let reqHead := (Request.get target
      |>.header! "Host"       host
      |>.header! "Connection" "close").line
    -- connect, send the request, and read the full response
    let client  TCP.Socket.Client.mk
    (client.connect sockAddr).block
    (client.send (Encode.encode (v := .v11) .empty reqHead).toByteArray).block
    let mut raw : ByteArray := .empty
    let mut done := false
    while !done do
      match  (client.recv? 4096).block with
      | none       => done := true
      | some chunk => raw := raw ++ chunk
    (client.shutdown).block
    -- strip response headers; body follows the first blank line
    let response := String.fromUTF8? raw |>.getD ""
    return match response.splitOn "\r\n\r\n" with
    | _ :: rest => some (String.intercalate "\r\n\r\n" rest)
    | []        => none
  catch _ =>
    return none
i
def main (args : List String) : IO Unit := do
  let url := args.headD "http://httpbin.org/get"
  IO.println s!"fetching: {url}"
  match  fetchUrl url with
  | none      => IO.println "request failed"
  | some body =>
    IO.println s!"status: ok ({body.length} bytes)"
    match Json.parse body with
    | .error e => IO.println s!"JSON parse error: {e}"
    | .ok v    =>
      match v with
      | Json.obj m =>
        for (k, val) in m.toList do
          IO.println s!"  {k}: {val}"
      | _ => IO.println s!"body: {body}"
i
fetching: http://httpbin.org/get
status: ok (199 bytes)
  args: {}
  headers: {"X-Amzn-Trace-Id": "Root=1-6a199ea5-6764aa4b4ed01b5409c9bc65",
 "Host": "httpbin.org"}
  origin: "142.188.27.125"
  url: "http://httpbin.org/get"

Environment Variables

i
-- Read an environment variable, falling back to a default when unset
def getEnvOr (key default : String) : IO String :=
  return ( IO.getEnv key) |>.getD default
i
-- Parse one "KEY=VALUE" line; skip blank lines and # comments
def parseLine (line : String) : Option (String × String) :=
  let t := line.trimAscii.toString
  if t.isEmpty || t.startsWith "#" then none
  else
    match t.splitOn "=" with
    | [] | [_] => none
    | k :: rest =>
      let key := k.trimAscii.toString
      -- rejoin with "=" in case the value itself contains "="
      let val := (String.intercalate "=" rest).trimAscii.toString
      if key.isEmpty then none else some (key, val)

-- Parse a .env-style file into a list of (key, value) pairs
def parseEnvFile (text : String) : List (String × String) :=
  text.splitOn "\n" |>.filterMap parseLine
i
-- blank lines and comments are skipped
#guard parseLine ""        == none
#guard parseLine "# note"  == none

-- a simple KEY=VALUE line is parsed correctly
#guard parseLine "HOST=localhost" == some ("HOST", "localhost")

-- values may contain "=" (only the first "=" is the separator)
#guard parseLine "URL=http://x.com/a=b" == some ("URL", "http://x.com/a=b")

-- a multi-line file with blanks and a comment
#guard
  parseEnvFile "HOST=localhost\nPORT=5432\n# comment\n\nUSER=admin" ==
  [("HOST", "localhost"), ("PORT", "5432"), ("USER", "admin")]
i
def main : IO Unit := do
  -- Read individual environment variables
  let home  getEnvOr "HOME" "(not set)"
  let user  getEnvOr "USER" "(not set)"
  IO.println s!"HOME: {home}"
  IO.println s!"USER: {user}"
  -- Parse a .env-style config embedded as a string
  let config := "DB_HOST=localhost\nDB_PORT=5432\n# database name\nDB_NAME=myapp"
  IO.println "parsed config:"
  for (k, v) in parseEnvFile config do
    IO.println s!"  {k} = {v}"
i
HOME: /Users/gvwilson
USER: gvwilson
parsed config:
  DB_HOST = localhost
  DB_PORT = 5432
  DB_NAME = myapp

Exercises

Fix: Range Missing Its Top Value

i
-- mapToRange maps raw entropy to [lo, hi]; fix the modulus expression
-- BUG: divides by (hi - lo) instead of (hi - lo + 1), so hi is never reachable
def mapToRange (lo hi raw : Nat) : Nat :=
  lo + raw % (hi - lo)

-- when raw == hi - lo the result should be hi (the top of the range)
#guard mapToRange 0 5 5 == 5

-- the result should always be at most hi
#guard mapToRange 1 6 999  6

-- the result should always be at least lo
#guard mapToRange 3 9 0  3
hint
  • raw % (hi - lo) produces values in [0, hi - lo - 1], so the offset lands in [lo, hi - 1]
  • Change the divisor to hi - lo + 1 so the full range [0, hi - lo] is possible
  • With raw = hi - lo as a test case, (hi - lo) % (hi - lo + 1) == hi - lo, giving lo + (hi - lo) = hi

Fix: Wrong JSON Key Name

i
import Lean
open Lean

-- getStr looks up the wrong key; fix the lookup
def makePerson (name : String) (age : Nat) : Json :=
  Json.mkObj [("name", Json.str name), ("age", Json.num age)]

-- BUG: looks up "Name" (capital N) instead of "name"
def getStr (j : Json) (key : String) : Option String :=
  match j.getObjValAs? String "Name" with
  | .ok s  => some s
  | .error _ => none

-- extracting the name field should return the value passed to makePerson
#guard getStr (makePerson "Euler" 76)  "name" == some "Euler"
#guard getStr (makePerson "Noether" 53) "name" == some "Noether"

-- extracting a missing key should return none
#guard (getStr (makePerson "Gauss" 77) "email").isNone
hint
  • The function looks up "Name" (capital N) but JSON keys are case-sensitive
  • makePerson stores the field as "name" (lower case)
  • Change the literal "Name" to the key parameter that is passed in

Write: Pick From a List

i
-- Write a pure function that picks one element from a non-empty list by index
-- pick xs i returns xs[i % xs.length] so any Nat index is valid

def pick (xs : List String) (i : Nat) : Option String :=
  none  -- TODO

#guard pick ["a", "b", "c"] 0 == some "a"
#guard pick ["a", "b", "c"] 2 == some "c"
-- index wraps around: 3 % 3 == 0
#guard pick ["a", "b", "c"] 3 == some "a"
-- empty list returns none
#guard (pick [] 0).isNone
hint
  • Return none for an empty list: if xs.isEmpty then none
  • Otherwise use xs[i % xs.length]! to wrap the index around
  • List.get? is an alternative but requires a Fin; the ! accessor with modulo is simpler

Write: List JSON Object Keys

i
import Lean
open Lean

-- Write a function that returns all keys in a JSON object as a list of strings
-- Return an empty list for non-object JSON values

def jsonKeys (j : Json) : List String :=
  []  -- TODO

#guard jsonKeys (Json.mkObj [("a", Json.num 1), ("b", Json.num 2)]) == ["a", "b"]
#guard jsonKeys (Json.mkObj []) == []
-- non-object returns empty list
#guard jsonKeys (Json.str "hello") == []
#guard jsonKeys (Json.arr #[]) == []
hint
  • Json has a constructor Json.obj m where m is a Std.TreeMap.Raw String Json compare
  • Call m.toList to get a List (String × Json), then .map Prod.fst to extract just the keys
  • Match on | Json.obj m => ... and return [] for all other constructors

Fix: Unchecked JSON Parse Error

i
import Lean
open Lean

-- getPerson tries to parse a JSON string, but it doesn't check whether
-- parsing succeeded before calling getStr. Fix the error handling.
def getPerson (jsonStr : String) : Option String :=
  -- BUG: Json.parse can fail, but the error is not checked
  let json : Json := match Json.parse jsonStr with
    | .ok v => v
    | .error _ => Json.null
  match json.getObjValAs? String "name" with
  | .ok name => some name
  | .error _ => none

#guard getPerson "{\"name\": \"Ada\"}" == some "Ada"
#guard (getPerson "not json at all").isNone
#guard (getPerson "{\"age\": 42}").isNone
hint
  • Json.parse returns Except error json — the error case is lost
  • Replace let json : Json := … with match Json.parse jsonStr with
  • Return none in the | .error _ => case before trying to extract fields

Fix: URL Without Scheme

i
-- match code assumes the URL has a scheme; it doesn't handle the case
-- where scheme is missing. Fix the edge case.
def extractHost (url : String) : Option String :=
  -- BUG: does not handle case where "://" is missing
  let parts := url.splitOn "://"
  match parts with
  | scheme :: rest =>
    let hostPart := String.intercalate "://" rest
    match hostPart.splitOn "/" with
    | host :: _ => if host.isEmpty then none else some host
    | [] => none
  | [] => none

#guard extractHost "http://example.com/path" == some "example.com"
#guard extractHost "https://github.com/user/repo" == some "github.com"
-- The string "just-a-string" has no scheme; should return none
#guard (extractHost "just-a-string").isNone
#guard (extractHost "").isNone
hint
  • splitOn "://" on "just-a-string" returns ["just-a-string"] — a one-element list
  • The match arms assume at least two parts: scheme :: rest
  • Add a guard: if parts.length < 2 then none before destructuring

Fix: Untrimmed Env Keys and Values

i
-- parseEnvFile doesn't trim whitespace from keys or values. A line like
-- "  HOST = localhost  " should parse correctly. Fix the trimming.
def parseLine (line : String) : Option (String × String) :=
  -- BUG: no trimming, so "  HOST = localhost  " fails
  if line.isEmpty || line.startsWith "#" then none
  else
    match line.splitOn "=" with
    | [] | [_] => none
    | k :: rest =>
      let key := k
      let val := String.intercalate "=" rest
      if key.isEmpty then none else some (key, val)

def parseEnvFile (text : String) : List (String × String) :=
  text.splitOn "\n" |>.filterMap parseLine

#guard parseLine "HOST=localhost" == some ("HOST", "localhost")
#guard parseLine "  HOST = localhost  " == some ("HOST", "localhost")
#guard parseLine "# comment" == none

#guard
  parseEnvFile "  KEY = value  \n\n# note\nPORT=8080" ==
  [("KEY", "value"), ("PORT", "8080")]
hint
  • " HOST = localhost " has whitespace around both key and value
  • Call .trimAscii (or .trim) on k before the key check
  • Also trim val before returning the pair
  • The existing parseLine in the lesson already does this — compare with env.lean

Write: Password Generator

i
-- Write a pure function that generates a random-looking password of a
-- given length by picking characters from an alphabet using an index.
-- Use a simple seed-based approach (no IO needed for this exercise).

-- Pick the character at the given index from the alphabet, wrapping around.
def pickChar (alphabet : String) (index : Nat) : Char :=
  alphabet.toList[index % alphabet.length]!

-- Generate a password by using the seed to pick one character at a time.
-- Advance the seed with each pick using a simple LCG.
def generatePassword (length : Nat) (seed : Nat) : String × Nat :=
  let alphabet := "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
  ("", seed)  -- TODO

#guard
  let (pw, _) := generatePassword 8 12345
  pw.length == 8

#guard
  let (pw1, _) := generatePassword 8 42
  let (pw2, _) := generatePassword 8 99
  pw1 != pw2  -- different seeds produce different passwords

#guard
  let (pw, _) := generatePassword 0 1
  pw == ""
hint
  • Use a simple LCG: seed' = (1664525 * seed + 1013904223) % 4294967296
  • Pick one character using pickChar alphabet seed, then advance the seed
  • Recurse or use List.range length with a foldl accumulator
  • foldl pattern: start with ("", seed), for each step pick a char and update both

Write: JSON Deep Get

i
import Lean
open Lean

-- Write a function that navigates into a nested JSON object given a list
-- of key names. Return none if any key is missing or the value is not an object.
-- ["a", "b"] means: get "a", then get "b" from that object.

def jsonDeepGet (j : Json) (keys : List String) : Option Json :=
  none  -- TODO

#guard
  let obj := Json.mkObj [("a", Json.mkObj [("b", Json.str "found")])]
  match jsonDeepGet obj ["a", "b"] with
  | some (Json.str s) => s == "found"
  | _ => false

#guard jsonDeepGet (Json.mkObj []) ["a"] == none
#guard jsonDeepGet (Json.str "hello") ["a"] == none

#guard
  let obj := Json.mkObj [("a", Json.mkObj [("b", Json.num 1)])]
  jsonDeepGet obj ["a", "b"] == some (Json.num 1)
hint
  • If keys is empty, return some j (the current value)
  • Otherwise, match keys as k :: rest: check if j is Json.obj m
  • Use m.toList.find? (·.1 == k) to look up the next key
  • Then recurse with rest on the found value, or return none if the key is missing

Write: URL Query Parser

i
-- Write a pure function that parses the query string portion of a URL
-- into a list of (key, value) pairs. The query string is the part after "?".
-- e.g., "?name=Ada&lang=lean" → [("name", "Ada"), ("lang", "lean")]
-- Handle missing values: "?flag" should produce [("flag", "")].
-- Return an empty list if there is no query string.

def parseQuery (url : String) : List (String × String) :=
  []  -- TODO

#guard parseQuery "http://example.com?name=Ada&lang=lean" ==
  [("name", "Ada"), ("lang", "lean")]

#guard parseQuery "http://example.com/?key=val" ==
  [("key", "val")]

#guard parseQuery "http://example.com?flag" ==
  [("flag", "")]

#guard parseQuery "http://example.com" == []

#guard parseQuery "http://example.com?a=1&b=2&c=3" ==
  [("a", "1"), ("b", "2"), ("c", "3")]
hint
  • Find "?" in the URL: url.splitOn "?"
  • If there are fewer than 2 parts, return [] (no query string)
  • Split the query part on "&", then split each pair on "="
  • For a pair without "=" (like "flag"), use "" as the value
  • Use filterMap to handle malformed pairs