LCME Пятница, 26.05.2017, 00:50
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Форум » Билеты к экзаменам » Программирование » Функции работы со списками
Функции работы со списками
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 из 11
Поиск:

Copyright Freidom © 2017 Хостинг от uCoz