состав функций

Question

Мне нужно написать некоторую функцию NTimesComposition (f: (int * int -> int), n: int), которая получает некоторую функцию f и целое число n и после выполнения композиции f , n раз , вот так f (x, (f (x, f (x, y)))) <- (здесь, например, n = 3) я начал написать это на smlnj, но это кажется более сложным, чем я думал, заранее спасибо за любую идею: </p>

NTimesComposition(f:(int * int -> int), n:int)
    if n = 1 then fn(x,y) => f(x, y ) else NTimesComposition...//here I'm stuck, must be recurstion

Answer 1

Вы уже получили его для n = 1, и вы, скорее всего, просто забыли передать (x, y) в рекурсивном вызове для n> 1. Очевидно, что здесь должно быть что-то вроде fn (x,y) => f (x, ...), где ... часть, где ваши рекурсивные вызовы будут.

Если бы вы забыли (x,y) в рекурсивной части, сделав его fn (x,y) => NTimesComposition (f, n-1), то вы бы в итоге построили цепочку анонимных функций, столь же длинную, как описывает ваш аргумент n. Это может привести к другому типу вашей NTimesComposition функции в зависимости от того, что n вы предоставляете, что недопустимо из-за того, как работает система типов SML (Хиндли-Милнер).

Следующие две функции выполнят эту работу за вас

fun foo (f, 1) = (fn xy => f xy)
  | foo (f, n) = (fn (x,y) => f(x, foo (f, n-1) (x,y)))

и

fun baz (f, 1) xy = f xy
  | baz (f, n) (x,y) = f(x, foo (f, n-1) (x,y))

, где первый больше всего напоминает ваш код с использованием анонимной функции.