Computer Science from Scratch

Let ‘s do the lab on functions as data, and write our own map, trickle and pen up .

fun fun-plus-one(num :: Number, func :: (Number -> Number)) -> Number:
  func(num) + 1
end

>>fun-plus-one(16, num-sqrt)
>>5
>>fun-plus-one(3, num-sqr)
>>10

Try entering assorted built-ins, or one you wrote yourself, as the moment parameter to fun-plus-one. In case you get hung up on syntax ‘func ‘ parameter can by anything, and try manipulating the ( Number – > Number ) annotation to ( – > Number ) or remove the note completely to ( num, degree fahrenheit ) and the officiate calm works .
Map
We ‘re given test cases and asked to implement f-to-c and goldilocks, and given the rule for farad to c temperature unit conversion.

fun f-to-c(f-lst :: List) -> List:
  cases (List) f-lst:
    | empty => empty
    | link(f, r) => 
      link((f - 32) * (5/9), f-to-c(r))
  end
end

fun goldilocks(f-lst :: List) -> List:
  cases (List) f-lst:
    | empty => empty
    | link(f, r) =>
      if f > 90:
        link("too hot", goldilocks(r))
      else if f < 70:
        link("too cold", goldilocks(r))
      else:
        link("just right", goldilocks(r))
      end
  end
end
check:
  f-to-c([list: 131, 77, 68]) is [list: 55, 25, 20]
  goldilocks([list: 131, 77, 68]) is [list: "too hot", "just right", "too cold"]
end

map ( getaway ( x ) : ten + 1 end, f-lst ) the ‘x ‘ input is the element in each link in the list f-list, you are mapping over the unharmed list one element at a clock, applying the lambda routine to each chemical element and returning a new number. We are asked to implement goldilocks using map :

# lambda notation
fun goldilocks(f-lst :: List< Number>) -> List:
  f-lst.map(lam(x): if x > 90: "too hot" else if x < 70: "too cold" else: "just right" end end)
end
check:
  goldilocks([list: 131, 77, 68]) is [list: "too hot", "just right", "too cold"]
end

# shorthand syntax for lambdas from lab documentation 
fun goldilocks2(f-lst :: List< Number>) -> List:
  f-lst.map({(x): if x > 90: "too hot" else if x < 70: "too cold" else: "just right" end})
end
check:
  goldilocks2([list: 131, 77, 68]) is [list: "too hot", "just right", "too cold"]
end

.map ( ) is a built-in list method, where f-lst.map ( … ) means we are mapping over f-lst. We could have besides rewritten it like the follow case where we consume a function of type A ( number ) that produces a different type B ( string, boolean ) :

fun goldilocks(x :: Number) -> String:
  if x > 90:
    "too hot"
  else if x < 70:
    "too cold"
  else:
    "just right"
  end
end

fun goldbool(x :: Number) -> Boolean:
  if (x > 90) or (x < 70):
    false
  else:
    true
  end
end


fun generic-map(f :: (A -> B), f-lst :: List) -> List:
  map(f, f-lst)
end
check:
  generic-map(goldilocks, [list: 131, 77, 68]) is [list: "too hot", "just right", "too cold"]
  generic-map(goldbool, [list: 131, 77, 68]) is [list: false, true, false]
end

Write your own version of map. I used the documentation examples for function as check tests. Remember map consumes a function and a list, applies the function to each entrance in the number returning a new list .

fun my-map(func :: (A -> B), l :: List) -> List:
  cases (List) l:
  | empty => 
  | link(f, r) => 
  ... my-map(func, r)
check:
  my-map(num-to-string, [list: 1, 2]) is [list: "1", "2"]
  my-map(lam(x): x + 1 end, [list: 1, 2]) is [list: 2, 3]
  my-map(lam(x): true end, [list: "test", "test2"]) is [list: true, true]
end

Filter
inaugural two assignments are square forward to get you to used to using trickle, except you have to use string-to-code-points ( ) alternatively of any built-in string functions .

fun tl-dr(lol :: List, length-thresh :: Number) -> List:
  filter(lam(element): string-to-code-points(element).length() <= length-thresh end, lol)
end
check:
  tl-dr([list: "dkfjdkj", "hi", "dkfjk"], 2) is [list: "hi"]
  tl-dr([list: "corner", "case", ""], 2) is [list: ""]
  tl-dr([list: "a", "b", "c"], 0) is empty
end

fun eliminate-e(words :: List) -> List:
  doc: "I got 101 and 69 from string-to-code-points(e) and (E)"
  filter(lam(x): not((string-to-code-points(x).member(101)) or 
      (string-to-code-points(x).member(69))) end, words)
end
check:
  eliminate-e([list: "e"]) is empty
  eliminate-e([list: "there's", "no", "letter", "e", "here"]) is [list: "no"]
  eliminate-e([list: "hEy", "101e"]) is empty
end

lambda parameters can be a unmarried letter : filter ( getaway ( ten ) : ten > 1 end ) as it ‘s immediately apparent what that parameter is and it ‘s telescope is limited though you can add annotations like thrash ( x : : Number ). You can besides ignore the argument if you do n’t plan on using it replacing ten with underline. tax : implement our own version of trickle, which is exchangeable to what we did for map :

fun my-filter(func :: ( T -> Boolean), l :: List)-> List:
  cases (List) l:
    | empty => empty
    | link(f, r) =>
      ...   
  end
end
check:
  fun length-is-one(s :: String) -> Boolean:
    string-length(s) == 1
  end
  my-filter(length-is-one, [list: "ab", "a", "", "c"]) is [list: "a", "c"]
  my-filter(is-link, [list: empty, link(1, empty), empty]) is [list: link(1, empty)]
  my-filter(lam(x): x > 0 end, [list: 0, 1, -1]) is [list: 1]
end

Fold
Try the two tasks : list-product and list-max :

fun list-product(lon :: List) -> Number:
  fold(lam(acc, n): acc * n end, 1, lon)
end
check:
  list-product([list: 2, 2, 2]) is 8
  list-product([list: 0, 1, 2]) is 0
  list-product([list: -1, -1]) is 1
end

There ‘s a hemipterous insect in list-max to fix, try all negative examples Found by hypertext transfer protocol : //github.com/rand-anon-007

fun list-max(lon :: List) -> Number:
  fold(lam(acc, n): if n > acc: n else: acc end end, 0, lon)
end
check:
  list-max([list: -1, 1, 2]) is 2
  list-max([list: 0, -100, 1]) is 1
  list-max([list: 1/2, 3/4]) is 3/4
end

The problem is the storage battery needs to be initialized with the beginning prize of the list not 0 :

fun list-max(lon :: List) -> Number:
  fold(lam(acc, n): if n > acc: n else: acc end end, lon.get(0), lon)
where:
  list-max([list: -1, 1, 2]) is 2
  list-max([list: 0, -100, 1]) is 1
  list-max([list: 1/2, 3/4]) is 3/4
  list-max([list: -1, -2, -3]) is -1
  list-max([list: 0]) is 0
# list-max(empty) what about this case? what's the max of empty?
end

If the list is empty then long.get ( 0 ) raises an error :

fun list-max(lon :: List) -> Number:
  if lon == empty:
    0 # is this correct?
  else:
    fold(lam(acc, n): if n > acc: n else: acc end end, lon.get(0), lon)
  end
where:
  list-max([list: -1, 1, 2]) is 2
  list-max([list: 0, -100, 1]) is 1
  list-max([list: 1/2, 3/4]) is 3/4
  list-max([list: -1, -2, -3])  is -1
  list-max(empty) is 0
end

now we have to make design decisions, should it eval to 0 for empty since the soap of an empty number is nothing or should it raise an error that we can handle ?

fun list-max(lon :: List) -> Number:
  if lon == empty:
    raise("List can't be empty")
  else:
    fold(lam(acc, n): if n > acc: n else: acc end end, lon.get(0), lon)
  end
where:
  list-max([list: -1, 1, 2]) is 2
  list-max([list: 0, -100, 1]) is 1
  list-max([list: 1/2, 3/4]) is 3/4
  list-max([list: -1, -2, -3])  is -1
  list-max(empty) raises "List can't be empty"
end

Write your own fold :

fun my-fold(func :: (B, A -> B), acc :: B, l :: List) -> B:
  cases (List) l:
    | empty => acc
    | link(f, r) =>
      my-fold(func, func(acc, f), r)
  end
end
check:
  my-fold((lam(acc, elt): acc + elt end), 0, [list: 3, 2, 1]) is 6
  # set accumulator to something not 0
  my-fold((lam(acc, elt): acc + elt end), 10, [list: 3, 2, 1]) is 16

  fun combine(acc, elt) -> String:
    tostring(elt) + " - " + acc
  end

  my-fold(combine, "END", [list: 3, 2, 1]) is "1 - 2 - 3 - END"
  my-fold(combine, "END", empty) is "END"
end

That type touch func : : ( B, A – > B ) means the function you are taking as remark has 2 parameters, since fold has an accumulator .
Map2
Try the task for implementing who-passed, the second task we ‘re asked to write map2 ourselves :

# link(ff, rr) and link(f, r) can be called anything:
# ie: link(head-first, tail-first) or link(head-second, tail-second)

fun my-map2(func :: (A, A -> B), list1 :: List, list2 :: List) -> List:
  cases (List) list1:
    | empty => empty
    | link(f, r) =>
      cases (List) list2:
        | empty => empty
        | link(ff, rr) =>
          ... what goes here?
      end
  end
end
check:
  my-map2(string-append, [list: "mis", "mal"], [list: "fortune", "practice"])
    is [list: "misfortune", "malpractice"]
  my-map2(_ + _, [list: "mis", "mal"], [list: "fortune", "practice"])
    is [list: "misfortune", "malpractice"]
  my-map2(string-append, [list: "mis", "mal"], [list: "fortune"])
    is [list: "misfortune"]
  my-map2(string-append, [list: "mis", "mal"], empty)
    is empty
  # test type signature
  my-map2(lam(x, y): if (x > 0) and (y > 0): true else: false end end, [list: 0, 1], [list: 2, 3]) 
    is [list: false, true] 
end

The last tax, best-price, look on youtube what a basic demand function is. hera ‘s an model :

fun demand(price-increase :: Number) -> Number:
 doc: "1000 is approx demand of product at a fixed price"
  1000 - (60 * price-increase)
end

This means as the price increases, the measure demanded will decrease by 60 units meter the price increase, so if the price increase is 1, the demand is 1000 – 60.

Map vs Filter vs Foldl vs Foldr
map and trickle merely consider one component in a list at a time whereas fold can consider the integral list. You can implement both map and percolate with fold ( try it ). If you ‘ve noticed in the Pyret software documentation there is foldl and foldr :

import lists as L

L.foldl(lam(acc, x): acc + x end, 0, [list: 1, 2, 3])
# (((0 + 1)+ 2)+ 3)
# eval nested brackets first, left to right

L.foldr(lam(acc, x): acc + x end, 0, [list: 1, 2, 3])
# (1 +(2 +(3 + 0)))
# eval nested brackets right to left

here ‘s an exercise of why you ‘d want to use foldr, making your own map function :

import lists as L

fun my-map(func :: (A -> B), list1 :: List) -> List:
  L.foldr(lam(acc, x): link(func(x), acc) end, empty, list1)
where:
  my-map(num-to-string, [list: 1, 2]) is [list: "1", "2"]
  my-map(lam(x): x + 1 end, [list: 1, 2]) is [list: 2, 3]
  my-map(lam(x): true end, [list: "test", "test2"]) is [list: true, true]
end
reference : https://alltopus.com
Category : Lastest

Related Posts

Leave a Reply

Your email address will not be published.