Семинар 2

Поговорили про базовые примитивы, списки и т. п., что с функции можно передавать там и так далее, что в List прячется много библиотечных функций, типа head, nth, length. Продолжим с конца прошлого файла.



In [1]:

    
13 :: []









    Out[1]:





[13]

На самом деле всегда, когда мы пишем обычные списки, на самом деле это лишь синтаксический сахар для такой конструкции:



In [2]:

    
1 :: 2 :: 3 :: []









    Out[2]:





[1; 2; 3]

Кроме того, можно перечислять:



In [3]:

    
[1..4]









    Out[3]:





[1; 2; 3; 4]

Можно вернуть голову списка, хвост. Интересно, как работает с пустыми!



In [11]:

    
List.head [1..5]
[1..2..5] // С шагом 2 от 1 до 5.
[1..-2..-4]
// List.head [] // Будет ошибка, а что же еще!
List.tail [13] // Это будет пустой список!
List.isEmpty []









    Out[11]:





true

Давайте писать функцию проверки на пустоту самостоятельно.



In [15]:

    
List.empty = []
// let isEmpty x = if x = List.empty then true else false // Ужас.
let isEmpty x = x = List.empty

Сопоставление с образцом.



In [18]:

    
let isEmpty x = 
    match x with // Типа switch.
    | [] -> true // Если пуской список.
    | _ -> false // Подчеркивание, это как бы все, что угодно.



In [26]:

    
let isEmpty = function // Наперед, пока не вникаем.
    | [] -> true
    | _ -> false

Если хотим написать рекурсивную функцию, то используем let.



In [23]:

    
let rec length xs =
    if List.isEmpty xs
    then 0
    else 1 + length (List.tail xs)



In [24]:

    
let rec length xs =
    match xs with
    | [] -> 0
    | y :: ys -> 1 + length ys

Есть замечательный модуль Seq, представляющих некоторые последователности. В F# нет бесконечных списков (в отличие от Haskell), однако есть бесконечные последовательности. Это похоже на генераторы в Python.



In [25]:

    
[1, 2, 3, 4] // Список из кортежа (1, 2, 3, 4)









    Out[25]:





[(1, 2, 3, 4)]



In [27]:

    
Seq.take 4 (Seq.initInfinite (fun i -> i + 1)) // Тоже пока не вникаем.
// Интерпретатор остановился на первых четырех элементов.









    Out[27]:





seq [1; 2; 3; 4]

Упражнение написать take. Это поможет понять рекурсию.



In [30]:

    
let rec take n xs =
    if n = 0 then []
    else (List.head xs) :: (take (n - 1) (List.tail xs))

take 4 [1..10]









    Out[30]:





[1; 2; 3; 4]



In [37]:

    
let (a, b, c) = (1, 2, 3) // todo понять.



In [38]:

    
List.min ['a'..'z'] // Так тоже можно!









    Out[38]:





'a'



In [39]:

    
// todo раньше есть реализация get.
let elem what list = get list what > 0









    



/home/nbuser/input.fsx(2,22): error FS0039: The value or constructor 'get' is not defined

Но вообще можно использовать стандартную.



In [41]:

    
List.exists (fun x -> x = 2) [1..8]









    Out[41]:





true



In [59]:

    
let rec sum list =
    match list with
    | [] -> 0
    | y::ys -> y + (sum ys)
    
let max a b = if a > b then a else b

let rec maxEl list =
    match list with
    | [] -> int -Operators.infinity // Говнокодим, как можем!
    | y::ys -> max y (maxEl ys)

sum [1..5]
maxEl [1..5]
maxEl [1]









    Out[59]:





1



In [61]:

    
int -Operators.infinity // А что это на самом деле? Нижнее ограничение int.









    Out[61]:





-2147483648

Описать функцмю, которая для данного $n$ создает список из всех попарных чисел от 1 до $n$. То есть $n^2$ элементов. Подсказка: используем конкатенацию: [1;2;3] @ [5;6;7].



In [75]:

    
// Сначала напишем прибавление ко всем элементам 1.
let rec add x n =
    match x with
    | [] -> []
    | y::ys -> (y + n) :: (add ys n)
    
let rec listSq x =
    match x with
    | [] -> []
    | y::ys -> (add [y] (List.length x)) @ (listSq ys)
    
listSq [3..5] // Вызываем дьявола.









    Out[75]:





[6; 6; 6]



In [ ]: