Редактирование: МФСП, 04 семинар (от 22 сентября)

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

=Списки=

Списки в RSL — упорядоченный типизированный набор элементов, элементы могут повторяться. Список в угловых скобках, порядок важен, все элементы одного типа

<1, 3, 1, 5, 4>
 <false, true>

Для списков, как и для всех типов в rsl определены две операции: =, &ne;

Для списков определено два типа: T-list(для конечных), T-inflist(для бесконечных) (по ANSI); T&times;, T^&omega;

Определён пустой список: <>

пр. синтаксис <v1..vn>

Опр. синтаксис: <expr|limit>

Пример:
 <2&times;n|n in <0..3>>

<3..7> &equiv; < 3,4,5,6,7>
 <7..3 > &equiv; <>

Список может быть определён для любого типа, не только базового: множества, списка...

==Индексация==

Для того, чтобы добраться до элемента, используется операция index, "()", в которой указан номер элемента:
 <1,4,5,6>(2) = 4
 <2,5,3>,<3,1>>(2) = <3,1>
 <2,5,3>,<3,1>>(2)(2) = 1

Если по не существующему номеру, то возвращает chaos.

Операции со списками:

===Конкатенация===
Конкатенацию можно применять только к конечным спискам, второй элемент может быть и конечным, и бесконечным. Результат соответствующего типа
 l1^l2
 ^:T-list x T-inflist -> T-inflist

Head: Первый элемент
 hd: T^&omega; <math>\tilde\rightarrow</math> T
 hd<> = chaos

Tail: Хвост
 tl: T^&omega; <math>\tilde\rightarrow</math> T^&omega;
 tl<> = chaos

Len: длина списка
 len:T^&omega; <math>\tilde\rightarrow</math> Nat
 len<n|n &bull; is_prime> &equiv; chaos

===elems: Элементы===
 elems: T^&omega; <math>\tilde\rightarrow</math> T-infset
 Возвращает множество элементов списка

===inds: Индексы===
 inds: T^&omega; <math>\tilde\rightarrow</math> Nat-infset 
 inds FL={1..len FL}

==Задача==
Задача: пр. функцию length, которя вычисляет длину списка
 '''value'''
   length: T&times; &rarr; Nat
     length(l) &equiv; if l &ne; <> then 1 + length(tl l) else 0 end

length2: T&times; &rarr; Nat 
     length2(l) &equiv; card inds l

==Case==
Конструкция case:
 '''case''' ''cond'' '''of'''
   ''pattern1'' &rarr; ''expr1''
   ''pattern2'' &rarr; ''expr2''
   ...
   _ &rarr; ''def_expr''
 '''end'''

===Список чисел Фибоначчи===
 type Nat1= {n:Nat &circle; n > 0 }
 value Fib:Nat1->Nat1
       Fib(n) &equiv;  
 case n of  
       1->1
       2->2
       _->Fib(n-2)+Fib(n-1)
 end

=== ===
 '''value''' rev:int-list&times; &rarr; T&times;
     rev(l) &equiv; 
 case L of 
 <> -> <> 
 <i>^L2 -> rev(L2)^< .i>
 end

Как это используется для работы со списками (на том же примере):
 '''value'''
   length: T&times; &rarr; Nat
     length(l) &equiv;
       '''case''' l '''of'''
         <> &rarr; 0
         &lt;i>^lr &rarr; length(lr) + 1
       '''end'''

Задача. Определить функцию Pascal, генерирующую треугольник Паскаля до уровня n включительно. Результат --- список списков. Например:
 <<1>,
  <1,1>,
  <1,2,1>,
  <1,3,3,1>,
  <1,4,6,4,1>>

'''type'''
   T1={i | i:Nat &bull; i &ge; 1}
 
 '''value'''
   pascal:T1 &rarr; (T1&times;)&times;
     pascal(i) &equiv; if i=1 then <<1>> else pascal(i-1)^<<1>^<pascal(i-1)(i-1)(j)+pascal(i-1)(i-1)(j-)|j:T1 &bull; j in <2..i-1>>^<1>>

Задача. Реализовать функцию rev, которая возвращает реверсивную версию списка.

'''value'''
   rev:T&times; &rarr; T&times;
     rev(l) &equiv; if l = <> then <> else rev(tl l)^ hd l end

Нерекурсивно, с пробеганием индекса

'''value'''
   rev:T&times; &rarr; T&times;
     rev(l) &equiv; <l(len(l)+1-n)|n in <1..len(n)>>

Даны следующие типы:
 '''type'''
   Page=Line&times;,
   Line=Word&times;,
   Word

(стандартный тип text в rsl на самом деле text=char&times;)

Для таких типов требуется определить функцию is_on, проверяющую, встречается ли данне слово на странице

'''value'''
   is_on: Word &times; Page &rarr; Bool
     is_on(w,p) &equiv; if p=<> then False else w &isin; elems hd p &or; is_on(w, tl p) end
 
   is_on: Word &times; Page &rarr; Bool
     is_on(w,p) &equiv; &exist; i : Nat &bull; (i &isin; {1..len(p)}) &and; (w &isin; elems p(i))

Определить number_of, подсчитывающую количество вхождений слов в страницу

'''value'''
   number_of: Word &times; Page &rarr; Nat
     number_of(w,p) &rarr; if p=<> then 0 else number_of_line(w,l) + number_of(w, tl p)
 
   number_of_line: Word &times; Line &rarr; Nat
     number_o_line(w,l) &rarr; if l=<> then 0 else (if w=hd l then 1 else 0) + number_of_line(w, tl l)
 
 
   number_of: Word &times; Page &rarr; Nat
     number_of(w,p) &rarr; card {(i,j)|(i:Nat&bull;j:Nat; &bull; p(i)(j)=w &and; i&isin; p &and; &isin;p(i)}

=== еще задачки ===
является упорядоченным?
 value isStore: Int-list &right; bool
 isStore(l)= &forall; i:int &bull; i >= 1; &and; i < len(l) => l(i+1) > l(i)

==== длина списка ====
 value len2: Elem-list-> Nat
 len2(E) &equal; ( if (E=<>) then 0 else 1+len2(tl E ) end )

len3(E) - card inds E
==== удаляем  заданный элем-т из списка ====
 value del: E-list &times; E &rarr; E-list
       del(l, x): &equal; < E(i) | i in <1..len L > &bull; L(i) != x >

==== подсчет ====
 value numOf: E-list &times; E -> Int
 NumberOf(L,x) = if ( LL=<> ) then 0 else
     if( hd(L) = x ) then NumberOf( tl L, x ) +1 else NumberOf( tl L, x)

==отображения==
<math>[3 \rightarrow , 5 \rightarrow false](1) = chaos</math>

операция взятия домена

<math>dom:(T[d] \overset{m}{\rightarrow} T[r] ) \rightarrow T[d]-infset</math>

<math>rng:(T[A] \overset{m}{\rightarrow} T[r] ) \rightarrow T[r]-infset</math> 
{{МФСП}}
{{Lection-stub}}

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%9C%D0%A4%D0%A1%D0%9F%2C_04_%D1%81%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80_%28%D0%BE%D1%82_22_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29