|
Функции работы со списками
|
|
| freidom | Дата: Понедельник, 22.12.2008, 15:29 | Сообщение # 1 |
 Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| Первая часть экзамена - функции работы со списками.
План описания:
1) Сигнатура типа.
2) Реализация функции.
3) Назначение функции.
4) Пример исползования функции.
|
| |
| |
| freidom | Дата: Понедельник, 22.12.2008, 15:35 | Сообщение # 2 |
|
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| 1. List.map
1) ('a -> 'b) -> 'a list -> 'b list
Code 2) let rec map f l =
match l with
l1::ls -> (f l1)::map ls
|[] -> [];;
3) Функция производит операцию f со всеми элементами списка.
4) Декартово произведение двух списков:
Code let dekmult l1 l2 =
flatten (map (fun a -> (map (fun b -> (b, a) l2))) l1;; |
| |
| |
| freidom | Дата: Понедельник, 22.12.2008, 15:35 | Сообщение # 3 |
|
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| 2. List.map2
1) ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
Code 2) let rec map2 f l1 l2 =
match (l1, l2) with
(l11::l1s, l21::l2s) -> (f l11 l21)::map2 f l1s l2s
|([], []) -> []
|_ -> failwith "?";;
3) Функция производит операцию f с каждым элементом I и II списка, записывая результат в III список.
4) Треугольник Паскаля
Code let next_line l =
map2 (+) ([0]@l) (l@[0]);;
let gen' n =
if n <= 0 then [[1]]
else match gen' (n - 1) with
ln::lp -> (next_line ln)::ln::lp
|_ -> failwith "?";;
let gen n = List.rev (gen' n);;
|
| |
| |
| freidom | Дата: Понедельник, 22.12.2008, 15:43 | Сообщение # 4 |
|
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| 3. List.iter
1) ('a -> unit) -> 'a list -> unit
Code 2) let iter f l =
match l with
l1::ls -> f l1; iter f ls
|[] -> ();;
3) Функция выполняет операцию со всеми элементами списка, не возвращая результата.
4) Печать списка
Code let print_list =
iter (fun x -> print_int x; print_string " ");; |
| |
| |
| freidom | Дата: Понедельник, 22.12.2008, 15:52 | Сообщение # 5 |
|
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| 4. List.fold_left
1) ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
Code 2) let rec fold_left f acc l =
match l with
l1::ls -> fold_left f (f acc l1) ls
|[] -> [];;
3) Сначала функция берёт два аргумента - аккумулятор и первый элемент списка и скармливает их функции f. Затем результат берётся в качестве первого аргумента, а вторым аргументом становится второй элемент списка, и так далее. Получается, что функция как бы сворачивает список, последовательно выполняя операцию f со всеми его элементами.
4) Среднее арифметическое списка
Code let midar l =
(fold_left (+) 0 l) / List.length l;; |
| |
| |
| freidom | Дата: Понедельник, 22.12.2008, 16:02 | Сообщение # 6 |
|
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| 5. List.filter
1) ('a -> bool) -> 'a list -> 'a list
Code 2) let filter f =
let rec find acc l =
match l with
[] -> rev acc
|l1::ls -> if f l1 then find (l1::acc) ls
else find acc ls in
find [];;
3) Функция оставляет в списке только те элементы, которые соответствуют правилу f.
4) Быстрая сортировка
Code let rec qsort l =
match l with
[] -> []
|l1::ls -> qsort (filter (fun x -> x < l1) ls) @ [l1] @
qsort (filter (fun x -> x >= l1) ls);;
Ещё 2 варианта реализации:
Code let bad_filter f l =
flatten (map (fun x -> if f x then [x] else []) l);;
Code let (>>) x f = f x;;
let bad_filter f l =
l >> map (fun x -> if f x then [x] else []) >> flatten;; |
| |
| |
| freidom | Дата: Понедельник, 22.12.2008, 16:12 | Сообщение # 7 |
|
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| 6. List.flatten
1) ('a list) list -> 'a list
Code 2) let flatten l =
match l with
l1::ls -> l1 @ (flatten ls)
|[] -> [];;
3) Функция превращает список списков в список, как бы уплощая его.
4) Декартово произведение (смотри билет 1).
|
| |
| |
| freidom | Дата: Понедельник, 22.12.2008, 16:19 | Сообщение # 8 |
|
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| 7. List.rev
1) 'a list -> 'a list
Code 2) let rev l =
let rec rev' l r =
match l with
l1::ls -> (rev' ls) (l1::r)
|_ -> r
in rev' l [];;
3) Функция возвращает список в обратном порядке.
4) Треугольник Паскаля (смотри билет 2).
|
| |
| |
| freidom | Дата: Понедельник, 22.12.2008, 16:24 | Сообщение # 9 |
|
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| 8. List.nth
1) int -> 'a list -> 'a
Code 2) let nth n l =
match l with
l1::ls -> if n = 0 then l1 else nth (n - 1) ls
|[] -> failwith "Error"
3) Функция возвращает n-ный элемент данного списка.
4) Медиана списка
Code let median l =
nth ((List.length l) / 2) l;; |
| |
| |
| freidom | Дата: Понедельник, 22.12.2008, 16:37 | Сообщение # 10 |
|
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| 9. List.length
1) 'a list -> int
Code 2) let rec length l =
match l with
[] -> 0
|l1::ls -> 1 + length ls;;
3) Функция возвращает длину данного списка.
4) Среднее арифметическое списка (смотри билет 4).
Медиана списка (смотри билет 7).
|
| |
| |
| freidom | Дата: Понедельник, 22.12.2008, 16:42 | Сообщение # 11 |
|
Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
| 10. (@)
1) 'a list -> 'a list -> 'a list
Code 2) let rec (@) l1 l2 =
match l1 with
l11::l1s -> l11::l1s @ l2
|[] -> l2;;
3) Функция объединяет 2 списка.
4) Треугольник Паскаля (смотри билет 2).
|
| |
| |
