Как переменные в сопоставлении с образцом допускают пропуск параметров?

Я делаю домашнее задание, но я застрял на чем-то на несколько часов. Я уверен, что это действительно тривиально, но я до сих пор не могу понять это после того, как просмотрел всю доступную документацию. Может ли кто-нибудь дать мне руку? По сути, упражнение по программированию OCaml требует определить функцию x^n с возведением в степень по алгоритму возведения в квадрат.

Я посмотрел решение:

   let rec exp x = function
    0 -> 1
   | n when n mod 2 = 0  -> let y = exp x (n/2) in y*y
   | n when n mod 2 <> 0 -> let y = exp x ((n-1)/2) in y*y*x
   ;;

Чего я, в частности, не понимаю, так это того, как параметр n может быть опущен в операторе fun и почему его следует использовать в качестве переменной для совпадения с x, что не имеет очевидной связи с определением возведения в степень путем возведения в квадрат.

Вот как бы я это сделал:

   let rec exp x n = match n with
   0 -> 1
   | n when (n mod 2) = 1 -> (exp x ((n-1)/2)) * (exp x ((n-1)/2)) * x
   | n when (n mod 2) = 0 -> (exp x (n/2)) * (exp x (n/2))
   ;;

functional-programming exponentiation pattern-matching ocaml
person rickmeizter    schedule 21.10.2012    source источник
comment
Если вы измените первое и второе вхождения n во втором фрагменте кода на другое имя переменной, но оставите остальные как n, код все равно будет работать. Вы понимаете, почему?   -  person sepp2k    schedule 21.10.2012
comment
@ sepp2k да, я понимаю, что буду использовать переменную для совпадения материала с n. Чего я не понимаю, так это почему первый фрагмент использует функцию (которая, насколько мне известно, в данном контексте является синтаксическим сахаром для сопоставления x с) и умудряется работать, хотя, как я вижу, он проверяет значение x, а не n, как того требует определение функции.   -  person rickmeizter    schedule 21.10.2012

Ответы (2)


arrow_upward
2
arrow_downward

Ваша версия синтаксически верна, дает хороший ответ, но долго выполняется. В вашем коде exp вызывается рекурсивно дважды, что приводит к вдвое большему количеству вычислений, каждый вызов дает в два раза больше вычислений и т. д. вплоть до n=0. В решении exp вызывается только один раз, результат сохраняется в переменной y, затем y возводится в квадрат.

Теперь о синтаксисе.

let f n = match n with
  | 0 -> 0
  | foo -> foo-1

эквивалентно:

let f = function
  | 0 -> 0
  | foo -> foo-1

Строка let rec exp x = function — это начало функции, которая принимает два аргумента: x и безымянный аргумент, используемый при сопоставлении с образцом. При сопоставлении с образцом строка

 | n when n mod 2 = 0  ->

называет этот аргумент n. Не то чтобы в каждом случае сопоставления с образцом можно было использовать разные имена (даже если это было бы менее понятно):

| n when n mod 2 = 0  -> let y = exp x (n/2) in y*y
| p when p mod 2 <> 0 -> let y = exp x ((p-1)/2) in y*y*x
person jrouquie    schedule 21.10.2012
comment
ОП не спрашивал о lets. - person sepp2k; 21.10.2012
comment
Спасибо за подсказку по поводу лета! Теперь я вижу, что при использовании функции я эффективно объявляю, что функция принимает еще один последний параметр после последнего, объявленного в предложении let. Мне удалить вопрос? - person rickmeizter; 21.10.2012
comment
Нет, оставьте вопрос, он может быть полезен кому-то еще: stackoverflow.com/faq - person jrouquie; 21.10.2012

arrow_upward
1
arrow_downward

Ключевое слово «функция» не является синтаксическим сахаром для

match x with

но для

fun x -> match x with

таким образом

let rec exp x = function

может быть заменен на

let rec exp x = fun y -> match y with

что, конечно, эквивалентно вашему решению

let rec exp x y = match y with

Обратите внимание, что я написал «y», а не «n», чтобы избежать путаницы. Переменная n, введенная после совпадения, является новой переменной, которая связана с параметром функции только потому, что соответствует ему. Например, вместо

let y = x in ...

вы могли бы написать:

match x with y -> ...

В этом выражении сопоставления выражение "y" соответствует "шаблону". И, как любой шаблон, он связывает свои переменные (здесь y) с соответствующим значением. (здесь значение x) И, как и в любом шаблоне, переменные в шаблоне являются новыми переменными, которые могут затенять ранее определенные переменные. В вашем коде:

let rec exp x n = match n with
  0 -> 1
  | n when (n mod 2) = 1 -> (exp x ((n-1)/2)) * (exp x ((n-1)/2)) * x
  | n when (n mod 2) = 0 -> (exp x (n/2)) * (exp x (n/2))
;;

переменная n в обоих случаях затеняет параметр n. Однако это не проблема, поскольку две переменные с одинаковыми именами имеют одинаковое значение.

person Valentin Perrelle    schedule 23.10.2012