CODEWITHSUNDEEP
smlml
Soya Aja
Soya Aja

Reputation: 31

ML; composite function n times

How is it possible to composite function f n times in ML?

composite two times;f(fx) composite three times;f(f(fx))) composite n times; f(f(f(f.....(fx)))))))

I have tried;

fun composite f g =
          let h x = f(g x)
            in h end;

fun repeat f n =
       if n = 0 then x 
       else composite f repeat(f (n - 1));

Thank you

Upvotes: 3

Views: 1485

Answers (2)

sshine
sshine

Reputation: 16135

When you write recursive functions, divide your problem into general, recursive cases, and base cases that don't require recursion. For example, composing a function with itself n times sounds like the base case might be either when n = 0 or when n = 1 (either could work; I'll get back to that).

I'd encourage pattern matching, but when recursing integers, if-then-else do seem just as simple. In any case, all the examples have been written in both styles. A simple skeleton might be:

fun repeat f n =
    if n = 0
    then ?
    else ?

fun repeat f 0 = ?
  | repeat f 1 = ?
  | repeat f n = ?

On functions that return functions

I imagine some of the difficulty here is that repeat must return a function. Syntactically you can achieve that in various ways. Like John suggests, you might write it by extending repeat with x:

fun repeat f n x =
    if n = 1
    then f x
    else ...

fun repeat f 1 x = f x
  | repeat f n x = ...

to which the natural, but slightly weird, interpretation is "repeat is a function that takes three arguments; the function f, the number of times it must be applied n, and f's argument x (?!)".

Alternatively, one might also write it like

fun repeat f n =
    if n = 1
    then (fn x => f x)
    else ...

fun repeat f 1 = (fn x => f x)
  | repeat f n = ...

which might be interpreted like "repeat is a function that takes two arguments; the function f and the number of times it must be applied n, and returns a function that applies f to its argument n times."

Those definitions are really equivalent. You'll see that by translating the description into types:

  • val repeat : ('a -> 'a) -> int -> 'a -> 'a
  • val repeat : ('a -> 'a) -> int -> ('a -> 'a)

That last parenthesis is implied in the first type signature.

Sometimes it helps to think of functions with many curried arguments as "functions with many arguments", and other times it helps to think of them as "functions that return functions that take yet other arguments". And repeat seems to be a mixture of this; n is best thought of as "a second argument", but x is best thought of as "the argument that the function we're returning takes".

With this preference, and a preference for pattern matching, my recommended basis would be:

fun repeat f 0 = ...
  | repeat f 1 = f
  | repeat f n = ...

since (fn x => f x) and f are really one and the same function.

On the base case and the recursive case

You write:

fun repeat f n =
    if n = 0 then x 
    else composite f repeat(f (n - 1));

  1. The x in then x has the wrong type, since repeat f n must return a function. See above.

  2. The case when applying f zero times is a little tricky. Whatever the result is, it should be the case that repeat f 0 should give the same result regardless of f. Or put differently, that f isn't applied, although the repeat f 0 does need to return something.

  3. On the recursive case, really, you're just messing up the parentheses. John revealed the o operator that is Standard ML's built-in version of composite which I'll prefer, too:

    composite f (repeat f (n-1))
f o repeat f (n-1)

    What you need to know about parentheses in Standard ML: You add them mostly to group things. When you write composite f repeat (f (n-1)), what you're saying is: "composite is a three-argument function that takes f, repeat and f (n-1) as an argument" and "f is a function that takes integers as arguments."

    When what you really wanted to say was "composite takes f and the result of composing f with itself n–1 times, and composes those." It's a classic mistake when you come from languages that expect function calls to look like foo(arg1, arg, arg3) and one thinks this translates into foo(arg1 arg arg3) when in fact you wanted foo arg1 arg2 arg3. In Standard ML, this parenthesis forces arg1 to be treated as a function and applies it to arg2 and arg3, and applies foo to the result of that. Whoops!

Upvotes: 4

John Coleman
John Coleman

Reputation: 52008

Your ideas are close to being correct. You could use currying to make them work:

fun composite f g x = f(g(x));

SML infers its type as:

val composite = fn : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b

which is exactly right for composition. Function application is left-associative, so 

composite f g x

parses as 

(composite f g) x

the function definition thus reads as giving the meaning of applying the function (composite f g) to an argument x. The meaning is, of course, to return the value f(g(x)).

You can test it:

fun square x = x*x
fun increment x = x + 1
val h = composite increment square

Then e.g. h 5 evaluates to 26 as expected.

A similar tweak works for your second definition. It could begin:

fun repeat f n x =

since this seems like homework, I'll leave the details to you, but your current attempt is rather close to a correct solution.

Having said all this, you should know that composition is a built-in operator in SML, denoted by the lowercase o, and that (op o) could be used in your second definition in place of composite.

Upvotes: 2

Related Questions