задачки по СМЛ, функциональное программирование Опции

[Bard]

Всем здраво! У меня тут в универе начали СМЛ прходить как ввод в Функциональное программирование. Никак не могу разобраться с этим языком. Надеюсь на вашу помощь, если вообще кто-то разбираеться в этом...
На Паскале или Си я бы код с закрытыми глазами написал, но тут не все так просто...

Вот 3 очень простые задачки:

1) Построить функцию removeDupl типа string которая уберет все подряд повторяющиеся элементы заданной строки и оставит только одну из них.

подпись функции: val removeDupl = fn : string -> string

пример:

-removeDupl("aabbacccddd");

val it = "abacd" : string


2) Построить функцию triangle типа int list list которая по заданному N выдаст список списков по которым можно построить треугольник высоты N.

подпись функции: val triangle = fn : int -> int list list

пример:

-triangle(4);

val it = [[1],[1,1],[1,1,1],[1,1,1,1]]



3) Построить функцию getNlargest типа int list которая по заданному N и списку чисел выдаст самые большие N чисел из заданного списка чисел.

подпись функции: val getNlargest = fn : int -> int list -> int list

пример:

- getNLargest 7 [1,2,4,3,4,10,2,3,4,32,6,6,4,7];

val it = [32,10,7,6,6,4,4] : int list


вот и все. у кого какие идеи? я думаю что во всех задачах такого типа в СМЛ без рекурсии никак.

Спасибо заранее...

[Bard]

Для последней задачи алгоритм я нашел... даже код написал но что то не компилиться

fun f(nil, N) = nil;
| f(list , 0) = list;
| f(list ,N ) = [[b]max(list)] @ f(exclude(list,max(list)),N-1);[/b]

просто тут 2 проблемы во первых как найти макс. элемент списка, во вторых как написать функцию exclude которая исключает макс. элемент списка.

кто нибудь знает синтаксис СМЛ?

[volvo]

Я, конечно, не специалист по функциональным языкам, но:
fun f(nil, N) = nil;
| f(list , 0) = list;
| f(list ,N ) = [max(list)] @ f(exclude(list,max(list)),N-1);

Выделенное красным - явно лишнее

[Bard]

Я, конечно, не специалист по функциональным языкам, но:
fun f(nil, N) = nil;
| f(list , 0) = list;
| f(list ,N ) = [max(list)] @ f(exclude(list,max(list)),N-1);

Выделенное красным - явно лишнее

Ну да это понятно... вопрос в том что нет такого понятия exclude в SML. надо самому эту функцию написать... а вот как не знаю

[volvo]

Нету, надо написать функцию, которая удалит все вхождения элемента X в список L:

- fun exclude(x, L) =
= if (L = []) then []
= else (if (x = hd(L))
= then exclude(x, tl(L))
= else hd(L)::exclude(x, tl(L)));

С максимумом разберешься?

[Bard]

Отлично!!! Спасибо огромное volvo! Но пока не идеально работает. Остался последний шаг.

вот код программы:

Код

fun max [x] = x
   | max (x::xs) = let val m = max xs in if x > m then x else m end

fun exclude(x1, L) =
if (L = []) then []
else (if (x1 = hd(L))
then exclude(x1, tl(L))
else hd(L)::exclude(x1, tl(L)));

fun f(nil, N) = nil
| f(m, 0) = m
| f(m, N) = [max(m)]@f(exclude(max(m),m), N-1);

нам нужно чтобы он удалял не все вхождения Х а только ту которая проверяться на этом шагy.

Сообщение отредактировано: Bard - 1.10.2009 0:14

[Bard]

Для ввода:

[1,2,4,3,4,10,2,3,4,32,6,6,4,7] 7

ответ должен быть:

[32,10,7,6,6,4,4]

а моя прога выдает:

[32,10,7,6,4,3,2,1]

[volvo]

нам нужно чтобы он удалял не все вхождения Х а только ту которая проверяться на этом шагy.

Это достигается небольшой корректировкой exclude:

- fun exclude(x, L) =
= if (L = []) then []
= else (if (x = hd(L))
= then tl(L)
= else hd(L)::exclude(x, tl(L)));

, функция работает:

- exclude(1, [2, 1, 3, 1, 5, 4, 1]);
val it = [2,3,1,5,4,1] : int list

, то, что нужно, правда? Только теперь F возвращает какой-то бред по-моему. Проверь у себя, может, я ошибся где-то?

[volvo]

Да, это в F ошибка, вот так надо:

fun f(nil, N) = nil
| f(m, 0) = nil
| f(m, N) = [max(m)]@f(exclude(max(m),m), N-1);

Понимаешь, что происходит? Когда второй параметр = 0, должен вернуться ПУСТОЙ список, тогда результат будет содержать именно столько элементов, чему был равен второй параметр изначально...

[Bard]

Ну помоему интересная тема... я продолжу

Тут такая задачка. У меня с алгоритмизацией все ок только как всегда проблема с грамматикой СМЛ. короче простенькая задачка. Надо отсортировать элементы заданного списка в убывающем или возрастающем порядке в зависимости от запроса.

подпись: val it = fn : (''a * ''a -> bool) -> ''a list -> ''a list

пример:

- sort op< [4,2,6,1,7];
val it = [1,2,4,6,7] : int list

- sort op> [4,2,6,1,7];
val it = [7,6,4,2,1] : int list

вот мое алго вставочным сортом:

Код

/*в возрастающем порядке*/
fun f(x,[])=[x]
   | f (x,xs as h::t)=if (x<h) then x::xs else h::(f(x,t))
val sort=List.foldr f [];

/*в убывающем порядке*/
fun f1(x,[])=[x]
   | f1 (x,xs as h::t)=if (x>h) then x::xs else h::(f1(x,t))
val sort1=List.foldr f1 [];

как мне добавить проверку на op> или op< чтобы в зависимости от запроса заработала нужная функция?

Сообщение отредактировано: Bard - 9.10.2009 6:23

[Bard]

Вот последний код:

Код

fun f(x,[])=[x]
  | f (x,xs as h::t)=if (x<h) then x::xs else h::(f(x,t))
val sort1 = List.foldr f [];

fun reverse(nil) = nil
  | reverse( x::xs) = reverse(xs)@[x];

fun sort (op<,L) = sort1(L)
  | sort (op>,L) = reverse(sort1(L));

но почему то не компилиться

где ошибка?