Функции работы со списками

[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]

Страница 1 из 1
1

Форум » Билеты к экзаменам » Программирование » Функции работы со списками

freidom

Дата: Понедельник, 22.12.2008, 15:29 | Сообщение # 1

Главный тут

Группа: Администраторы

Сообщений: 273

Репутация: 20

Статус: Offline

Первая часть экзамена - функции работы со списками.
План описания:
1) Сигнатура типа.
2) Реализация функции.
3) Назначение функции.
4) Пример исползования функции.

freidom

Дата: Понедельник, 22.12.2008, 15:35 | Сообщение # 2

Главный тут

Группа: Администраторы

Сообщений: 273

Репутация: 20

Статус: 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

Репутация: 20

Статус: 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

Репутация: 20

Статус: 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

Репутация: 20

Статус: 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

Репутация: 20

Статус: 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

Репутация: 20

Статус: 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

Репутация: 20

Статус: 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

Репутация: 20

Статус: 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

Репутация: 20

Статус: 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

Репутация: 20

Статус: 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).

Форум » Билеты к экзаменам » Программирование » Функции работы со списками

Страница 1 из 1
1