Lists and Arithmetic (Lecture 5 Part 2)

مقدمة
  • المحاضرة بتتكلم عن الـ List وهي محاضره دسمه جدا ومهمه جدا مينفعش تتكروت.
  • هنفهم المحاضرة دي إزاي الـ List بتتكون من Head و Tail، وإزاي بنعمل Unification بين الـ Lists.
  • هنتعلم العمليات الأساسية على الـ Lists زي الـ Membership، الـ Append، الإضافة، الحذف، التقسيم (Decomposing)، والتباديل (Permutations).

إيه هي الـ Lists؟

  • الـ List هي مجموعة من البيانات المرتبة (Ordered Data).
    • ممكن تحتوي على صفر أو أكتر من العناصر.
    • العناصر بتكون محطوطة بين أقواس مربعة [ ] وبتتصل ببعضها بفاصلة ,.

أمثلة:

  • ا [12, city, ann, bb] -> دي List فيها 4 عناصر.
  • ا [a] -> دي List فيها عنصر واحد بس.
  • ا [] -> دي Empty List (ليست فاضية).
  • ا [34, tom, [2,3]] -> دي List فيها 3 عناصر، والعنصر التاني عبارة عن List جواها عنصرين.

الـ Head والـ Tail

  • أي List (مش فاضية) نقدر نقسمها لجزأين أساسيين:
    1. الـ Head (الرأس): هو أول عنصر في الـ List.
    2. الـ Tail (الديل): هو باقي عناصر الـ List، ودايمًا الـ Tail لازم يكون List.
مثال

لو عندنا الـ List دي: [ann, tennis, tom, king]

  • الـ Head هنا هو ann
  • الـ Tail هنا هو [tennis, tom, king]
  • عشان نفصل الـ Head عن الـ Tail في Prolog بنستخدم الرمز | (Vertical bar):
|?- [a, b, c, d] = [Head | Tail].
Head = a, Tail = [b, c, d].

|?- [a] = [H | T].
H = a, T = [].   %  the Tail of one element is an Empty List

|?- [] = [H | T].
false.           %  Empty List does not have a Head or a Tail
l سحب أكتر من عنصر

نقدر نسحب أكتر من عنصر في البداية كـ Heads (يعني نعمل اتنين هيد او اكتر) ونخلي الباقي Tail:

|?- [H1, H2 | Tail] = [mia, vincent, jules, yolanda].
H1 = mia, H2 = vincent, Tail = [jules, yolanda].

الـ List Unification (التطابق)

  • الـ Lists ممكن يحصلها Unify (تتطابق) مع متغيرات أو مع Lists تانية.
  • عشان يحصل Unification بين 2 Lists، لازم يكون عندهم نفس الطول، وكل عنصر في الـ List الأولى يقدر يحصله Unify مع العنصر اللي بيقابله في الـ List التانية.

أمثلة:

|?- [Any, list, 'of elements'] = X.
X = [Any, list, 'of elements'].

|?- [a, B, c, D] = [A, b, C, d].
A = a, B = b, C = c, D = d.

|?- [[X, a]] = [b, Y].
false.      % طول الأولى 1 (فيها ليست واحدة)، وطول التانية 2

|?- [(a+X), (Y+b)] = [(W+c), (d+b)].
W = a, X = c, Y = d.

العمليات الأساسية على الـ Lists

  • العمليات دي تعتبر أهم جزء في الـ Lists، وكلها بتعتمد على فكرة الـ Recursion (إن الـ Rule بتنادي نفسها) وإننا بنقسم الـ List لـ Head و Tail. دلوقتي هنفهم كل عملية بتشتغل إزاي بالتفصيل:

1. الـ Membership ا member

  • العملية دي بتجاوب على سؤال: "هل العنصر ده موجود جوه الـ List ولا لأ؟"

  • عشان نعرف بتشتغل ازاي هنقسم الموضوع لجزئين:

    1. الـ Base Case (حالة التوقف): يعني بصيت في أول الليست (الـ Head) ولقيت الحاجة اللي بدور عليها.
    2. الـ Recursive Case (حالة التكرار): الحاجة الي بدور عليها مش في أول الليست، فهسيب اول الليست (الـ Head) وأروح أدور في باقي الليست (الـ Tail).

  • الحالة الأولى: العنصر X هو الـ head بتاع الليست:

member(X, [X | Tail]).
  • الحالة التانية: العنصر X مش هو الـ head ، فهنروح ندور عليه في الـ Tail 
member(X, [Head | Tail]) :- member(X, Tail).
  • فيبقي التعريف الكامل بتاعها : 
member(X, [X | Tail]).    
member(X, [Head | Tail]) :- member(X, Tail).
Trace

: ?- member(b, [a, b, c]).

  • الاول بنسال :
    1. هل b هي الـ Head a؟ لأ. (بندخل في الحالة التانية وندور في الـ Tail [b, c]).
    2. هل b هي الـ Head بتاع [b, c]؟ أيوة! (هنا الـ Base case بتتحقق ويرجع true).

2. الـ Concatenation (الدمج) append

  • بتستخدم عشان ندمج 2 lists في بعض ونطلع بـ List تالتة. append(L1, L2, L3).
  • فكرتها إننا بناخد عناصر اول List نشيلهم على جنب، لحد ما اول List تفضى، وبعدين ندمجها مع التانية، وبعدين نرجع العناصر اللي شيلناها.
  1. الـ Base Case: لو الـ List الأولى فاضية []، يبقى لو لزقناها مع أي List تانية L هيدينا نفس الـ List التانية L.
  2. الـ Recursive Case: لو الـ List الأولى مش فاضية، بناخد الـ Head بتاع اول List نحطه كـ Head للناتج النهائي، ونعمل append للـ Tail بتاع الـ List الاولي مع الـ List التانية.
  • لو الأولى فاضية، الناتج هو التانية
append([], L, L).
  • بناخد X من الأولى نحطه في الناتج، ونكمل دمج لباقي الأولى (L1) مع التانية (L2)
append([X | L1], L2, [X | L3]) :- append(L1, L2, L3).
  • فيبقي التعريف الكامل : 
append([], L, L).
append([X | L1], L2, [X | L3]) :- append(L1, L2, L3).
لو مش فاهم عادي انا كمان مش فاهم
  • مش لازم تفهم الـ definition بتاع الفانكشن عشان تحل ف لو مفهمتش اعرف هيا بتعمل ايه بس وبصمج شكلها زي ماهو
استخدامات تانية للـ append (التقسيم - Decomposing)

الحاجة المبهره هنا إنك لو عكست السؤال، هيعكس الإجابة, يعني لو إديته الناتج (الليست بعد الدمج)، هيقدر يقسملك الليست بكل الاحتمالات الممكنة:

?- append(L1, L2, [a,b,c]).
L1= [], L2 = [a,b,c];
L1= [a], L2= [b,c];
L1 = [a,b], L2 = [c];
L1 = [a,b,c], L2 = [];

3. الإضافة والحذف (Adding & Deleting)

الإضافة (Adding) add:

  • دي اسهل شوية, لو عايز تضيف عنصر X على List اسمها L، حطه هو الـ Head، وخلي L هي الـ Tail في List جديدة.
add(X, L, [X | L]).
% ?- add(5, [1,2], L). -> L = [5, 1, 2].

الحذف (Deleting) del:

  • شبه الـ member شوية، بنمشي ندور علي العنصر المطلوب بس لما بنلاقيه بدل ما بنجاوب بـاننا لقيناه، إحنا بنشيل العنصر ونرجع الـ List من غيره:

    1. لو العنصر X هو الـ Head، يبقى الـ List الجديدة هي الـ Tail وخلاص كده.
    2. لو العنصر X مش هو الـ Head، يبقى هنحتفظ بالـ Head زي ما هو Y، وننادي الدالة تاني تروح تمسح X من الـ Tail.

  • مسحنا X عشان هو الـ Head، ورجعنا Tail


del(X, [X | Tail], Tail).
  • احتفظنا بـ Y، ورحنا نمسح X من الـ Tail عشان نجيب Tail1 الجديد
del(X, [Y | Tail], [Y | Tail1]) :- del(X, Tail, Tail1).
  • فيبقي التعريف الكامل : 
del(X, [X | Tail], Tail).
del(X, [Y | Tail], [Y | Tail1]) :- del(X, Tail, Tail1).
  • (ملاحظة: لو العنصر X متكرر جوه الـ List، الـ Prolog بيمسح أول واحد يقابله، ولو دوست ; هيرجعلك الاحتمالات التانية إنه يمسح النسخ التانية ويسيب الأولى).
الـ insert في أي مكان باستخدام الـ del
  • دي حاجة شبه الي عملناها في الـ append نقدر نستخدم دالة الحذف عشان نضيف عنصر X في أي مكان في الـ List.
  • الفكرة انك لو عملت: "هات لي الـ BiggerList اللي لو حذفت منها X، يتبقى لي الـ L " ( بص في المثال عشان تفهم).
insert(X, L, BiggerList) :- del(X, BiggerList, L).

4. الـ sublist

  • عشان نختبر هل الـ List اللي اسمها S موجودة جوه الـ List الكبيرة L (بنفس الترتيب).
  • بنستخدم الـ append مرتين كأننا بنقطع الـ List الكبيرة حتت:
    1. بنقسم الـ L الكبيرة لجزأين: L1 و L2.
    2. بناخد الـ L2 نقسمها لجزأين: S (اللي بندور عليها) و L3 (الباقي).
  • لو عرفنا نعمل التقسيمة دي، يبقى أكيد S موجودة جوه L.
sublist(S, L) :- append(L1, L2, L), append(S, L3, L2).

الـ Sublist بتدور على الـ عناصر ورا بعض بنفس الترتيب.

مثال (1): هل دي Sublist ولا لأ؟

?- sublist([c,d,e], [a,b,c,d,e,f]).
true.

(عشان c,d,e موجودين ورا بعض).

مثال (2): العناصر موجودة بس مش ورا بعض!

?- sublist([c,e], [a,b,c,d,e,f]).
false.

(هيديك false لأن c و e مش ورا بعض في الليست الأساسية، مفصولين بـ d).

5. التباديل (Permutations) permutation

  • لو عندنا List وعايزين نجيب كل الترتيبات (التباديل) الممكنة لعناصرها.
  • الفكرة بتاعتها:
    1. لو الـ List فاضية، تباديلها هي قايمة فاضية.
    2. لو فيها عناصر، بناخد أول عنصر X على جنب، ونجيب التباديل بتاعة باقي الـ List L1، وبعدين نحط العنصر X في كل الأماكن الممكنة جوه الـ L1.
permutation([], []).
permutation([X | L], P) :- permutation(L, L1), insert(X, L1, P).

مثال (1): تباديل لعنصرين:

?- permutation([a,b], P). 
P = [a, b] ;
P = [b, a] ;
false.

مثال (2): تباديل لـ 3 عناصر:

?- permutation([red, blue, green], P). 
P = [red, blue, green]; 
P = [red, green, blue]; 
P = [blue, red, green]; 
P = [blue, green, red]; 
P = [green, red, blue]; 
P = [green, blue, red]; 
false.

Arithmetic and Lists

  • دي شوية أمثلة وتطبيقات جاهزة في الـ Prolog للتعامل مع الـ Lists:
  1. لو عايزين نجيب طول الـ List (Length):
  • الـ Prolog فيها الدالة الجاهزة length بس إحنا في المنهج غاويين وجع دماغ وهنكتبها بنفسنا:
len([], 0).
len([_ | L], N) :- len(L, X), N is X + 1.
  1. عكس الـ List (Reverse):
    الدالة الجاهزة reverse، تعريفها:
nrev([], []).
nrev([H | T], R) :- nrev(T, RevT), append(RevT, [H], R).
  1. جمع عناصر الـ List (Sumlist):
    عشان نجمع الأرقام اللي جوه الـ List:
sumlist([], 0).
sumlist([H | T], N) :- sumlist(T, N1), N is N1 + H.
  1. اختبار إن طول الـ List زوجي (Even):
    بنسحب كل مرة عنصرين، لحد ما نوصل لقايمة فيها عنصرين أو قايمة فاضية.
even([_,_]).
even([_,_ | T]) :- even(T).
قبل ما تدخل علي المحاضره الي بعدها حل امثلة المحاضرة والسكاشن من هنا : Chapter 5 (Part 2) - Practice

Nour Eldeen Mahmoud