#lang pyret

# It's very easy to write functions that can use for-syntax effectively.
# This function, when used in a for expression, approximates a for loop
# in languages like C and Java.
#
# Think of it as a generalized "each" function, but where the elements
# are not retrieved from a list in sequence but are generated by
# repeated applications of a function. The function each-loop in the tests
# shows that it is simple to build "each" from this.
fun loop(f, i :: { init :: Any, test :: (Any -> Boolean), next :: (Any -> Any) }) -> Nothing:
  doc: "A C-like loop construct."
  if i.test(i.init) block:
    f(i.init)
    loop(f, i.{ init: i.next(i.init) })
  else:
    nothing
  end
where:
  var sum = 0
  loop(lam(i): sum := sum + i end, { init: 0, test: _ < 10, next: _ + 1 })
  sum is 45

  sum := 0
  for loop(i from { init: 0, test: _ < 10, next: _ + 1 }):
    sum := sum + i
  end
  sum is 45

  sum := 0
  for loop(i from { init: 0, test: _ < -5, next: _ + 1 }):
    sum := sum + i
  end
  sum is 0

  sum := 0
  for loop(i from { init: 0, test: _ < 10,
                    next: lam(x): if num-modulo(x, 2) == 0: x + 1 else: 2 * x end end }):
    sum := sum + i
  end
  sum is 19

  fun each-loop(f, lst):
    loop(f, { init: lst, test: is-link, next: _.rest })
  end
  for loop(i from { init: 10, test: _ < 20, next: _ + 1 }) block:
    sum := 0
    nums = range(0, i)
    for each(elt from nums):
      sum := sum + i
    end
    cur-total = sum
    sum := 0
    for each-loop(elt from nums):
      sum := sum + i
    end
    sum is cur-total
  end
end

# Implementation of Pollard's rho algorithm for factoring numbers
fun gcd(a, b):
  doc: "Calculates the greatest common divisor of a and b using Euclid's algorithm."
  if b == 0: a else: gcd(b, num-modulo(a, b)) end
end

fun pollard-rho(n :: Number) -> Option block:
  doc: "Attempts to factor the given number using Pollard's rho algorithm."
  fun f-m(m):
    lam(x): num-modulo(((x * x) + m), n) end
  end
  var factor = none
  for loop(fs from { init: map(f-m, [list: -1,2,-3]),
                     test: lam(fs): is-none(factor) and is-link(fs) end,
                     next: _.rest }) block:
    f = fs.first
    var x = 2
    var y = 2
    var d = 1
    for loop(i from { init: nothing,
                      test: lam(_): d == 1 end,
                      next: lam(_): nothing end }) block:
      x := f(x)
      y := f(f(y))
      d := gcd(num-abs(x - y), n)
    end
    when d <> n:
      factor := some(d)
    end
  end
  factor
where:
  fun is-factor-of(n):
    lam(x):
      g = gcd(x.value, n)
      (g <> 1) and (g <> n)
    end
  end

  pollard-rho(3157) satisfies is-factor-of(3157)
  pollard-rho(4589) satisfies is-factor-of(4589)
  pollard-rho(5261) is none
  pollard-rho(6659) is none
  pollard-rho(7197) satisfies is-factor-of(7197)
  pollard-rho(8051) satisfies is-factor-of(8051)

  fun fermat(i): num-expt(2, num-expt(2, i)) + 1 end
  pollard-rho(fermat(3)) is none
  pollard-rho(fermat(4)) is none
  pollard-rho(fermat(5)) satisfies is-factor-of(fermat(5))
  pollard-rho(fermat(6)) satisfies is-factor-of(fermat(6))
end