البرمجة الوظيفية كمثال للعمل مع المصفوفات من نظرية الجبر الخطي

المقدمة


أساس العمل مع المصفوفات (في هذه المقالة سننظر فقط في المصفوفات ثنائية الأبعاد) هو نظرية رياضية قوية من مجال الجبر الخطي. يتبع تعريف أو إجراء من آخر ؛ وظيفة واحدة تستدعي أخرى. لذلك ، من أجل التنفيذ الوظيفي لوظيفة العمليات الحسابية على المصفوفات ، تتناسب اللغات الوظيفية بشكل جيد للغاية. في هذه المقالة ، سنلقي نظرة على أمثلة محددة في F # وسنقدم تعليقات مفصلة حول كيفية عمل ذلك. نظرًا لأن F # جزء من عائلة .NET ، يمكن استخدام الوظيفة الناتجة دون أي مشاكل في اللغات الحتمية الأخرى ، على سبيل المثال C #.

تعريف المصفوفة وتنفيذها في F #


المصفوفات هي الجزء الأساسي والأهم من الجبر الخطي. غالبًا ما تستخدم المصفوفات في البرمجة ، على سبيل المثال ، في النمذجة ثلاثية الأبعاد أو تطوير الألعاب. بالطبع ، تم اختراع الدراجة لفترة طويلة والأطر اللازمة للعمل مع المصفوفات جاهزة بالفعل ، ويمكن ويجب استخدامها. لا تهدف هذه المقالة إلى اختراع إطار عمل جديد ، ولكنها توضح تنفيذ العمليات الحسابية الأساسية للعمل مع المصفوفات بأسلوب وظيفي باستخدام لغة البرمجة F #. عندما نفحص المادة ، سننتقل إلى النظرية الرياضية للمصفوفات ونرى كيف يمكن تنفيذها في التعليمات البرمجية.

أولاً ، دعنا نتذكر ما هي المصفوفة؟ تقول لنا النظرية ما يلي
يسمى جدول مستطيل من الأرقام التي تحتوي على صفوف m وأعمدة n مصفوفة بحجم mxn

المصفوفات عادة ما يرمز لها بأحرف كبيرة من الأبجدية اللاتينية وتكتب باسم

A=(a11a12...a1na21a22...a2n............am1am2...amn)



أو قريبًا

A=(aij)



للعمل مع المصفوفات في F # ، سننشئ سجلاً بناءً على جدول ثنائي الأبعاد ، والذي سنقوم بتوسيعه بطرق مفيدة لإجراء العمليات الحسابية اللازمة عليه.

type Matrix = { values: int[,] }
    with
        //    
    end

أضف طريقة مساعدة لتهيئة التسجيل بمصفوفة ثنائية الأبعاد

static member ofArray2D (values: int [,]) = 
    { values = values }

وسيطة إدخال الدالة ستكون مصفوفة ثنائية الأبعاد ، وفي مخرجاتها ، سجل من نوع Matrix . فيما يلي مثال على تهيئة السجل.

let a = array2D [[1;0;2]
                 [3;1;0]]
let A = Matrix.ofArray2D a

المصفوفتان A = (aij) و B = (bij) تسمى متساوية إذا تزامنت مع عنصر ، أي aij = bij للجميع i = 1،2 ...، m و j = 1،2 ... n

لتطبيق هذه القاعدة ، سنستخدم عامل تجاوز == وسنضيف بعض الوظائف المفيدة ، والتي سنحتاجها أيضًا في المستقبل.

static member sizes matrix =
    let rows = matrix.values.[*,0].Length
    let cols = matrix.values.[0,*].Length
    (rows, cols)

static member isEquallySized matrix1 matrix2 =
    let dim1 = Matrix.sizes matrix1
    let dim2 = Matrix.sizes matrix2
    (dim1 = dim2)

static member (==) (matrix1, matrix2) =
    if not (Matrix.isEquallySized matrix1 matrix2) then false
    else
        not (matrix1.values
               |> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true)
               |> Seq.cast<bool>
               |> Seq.contains false)

دعونا نلقي نظرة فاحصة على الرمز أعلاه. كما ترون ، هناك ثلاث وظائف. تُرجع دالة الأحجام الأولى بُعد المصفوفة كمجموعة. نظرًا لأننا نعمل فقط مع المصفوفات المستطيلة ، للحصول على عدد الصفوف ، فإننا نأخذ شريحة كاملة من العمود الأول ونعيد طوله.

let rows = matrix.values.[*,0].Length

تحديد عدد الأعمدة يعمل بطريقة مماثلة - نحصل على شريحة كاملة من الصف الأول ونعيد طولها. تقارن

الدالة isEquallySized التالية أبعاد المصفوفتين وترجع القيمة الصحيحة إذا كانت متساوية. للقيام بذلك ، يستخدم وظيفة الأحجام الجاهزة ويقارن النتائج ببساطة.

يبدو العامل == لمقارنة مصفوفتين بشكل أكثر تعقيدًا ، ولكن الآن سترى أنه بسيط أيضًا.

قبل مقارنة مصفوفتين ، نقارن أبعادها. إذا لم تكن متساوية ، فلا توجد نقطة أخرى في التحقق ، حيث من الواضح بالفعل أن المصفوفات لن تكون متساوية.

if not (Matrix.isEquallySized matrix1 matrix2) then false

علاوة على ذلك ، على أساس المصفوفات الأصلية matrix1 و matrix2 ، نشكل مصفوفة جديدة مليئة بالصواب أو الخطأ ، اعتمادًا على ما إذا كانت الخلايا المقابلة لكل من المصفوفات تتزامن.

matrix1.values
|> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true

و Array2D.mapi وظيفة بالتكرار على كل عناصر matrix1 ويمر ثلاثة المعلمات
اكس إلى معالج - مؤشر الصف
ذ - مؤشر العمود
الخامس - خلية
محتويات قارنا محتويات الخلية الخامس مع الخلية المقابلة matrix2 وإذا كانت تساوي، ثم أكتب صحيحا ، وإلا كاذبة .

إذا كانت هناك خلية واحدة على الأقل تحتوي على عنصر خاطئ ، فهذا يعني أن المصفوفات ليست متساوية مع بعضها البعض.

نظرًا لأن Array2D لا يحتوي على طرق للتصفية أو البحث ، فسنطبق ذلك بأنفسنا. للقيام بذلك ، نقوم بتحليل المصفوفة إلى قائمة خطية

|> Seq.cast<bool>

والعثور على عدم تطابق واحد على الأقل

|> Seq.contains false

و Seq.contains وظيفة سيعود صحيح إذا واحد على الأقل كاذبة وجدت قيمة في القائمة الموسعة . لذلك ، نحتاج إلى عكس النتيجة بحيث يعمل عامل == بالطريقة التي نريدها

else
    not (matrix1.values
           |> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true)
           |> Seq.cast<bool>
           |> Seq.contains false)

المصفوفة O تسمى مصفوفة صفرية أو صفرية إذا كانت جميع عناصرها تساوي الصفر.


static member O rows cols =
    let array2d = Array2D.zeroCreate rows cols
    { values = array2d }

مثال على استخدام هذه الوظيفة

let AO = Matrix.O 5 5

أعتقد أنه لا يوجد شيء معقد يتطلب التفسير ، لذلك نستمر.
المصفوفة التي يساوي عدد صفوفها عدد الأعمدة ويساوي n تسمى مصفوفة مربعة من الترتيب n

وهكذا ، فإن المصفوفة المربعة لها الشكل.

A=[a11a12...a1na21a22...a2n............an1an2...ann]


كجزء من هذه القاعدة ، سننشئ وظيفة تحول مصفوفة مستطيلة إلى مصفوفة مربعة عن طريق قطع جميع العناصر التي لا تقع في المربع.

static member toSquare matrix =

    //    
    let dim = Matrix.sizes matrix

    //   
    let colCount: int = snd dim
    //   
    let rowCount: int = fst dim

    //    
    let length = System.Math.Min (colCount, rowCount)

    //      
    //     
    let zero = Array2D.zeroCreate length length

    //     
    let square = zero |> Array2D.mapi (fun x y _ -> matrix.values.[x, y])

    //   
    { values = square }

تشرح التعليقات في شفرة المصدر كيفية عمل الوظيفة ، لذا دعنا نواصل.
تسمى المصفوفة المربعة مثلثة إذا كانت جميع عناصرها تحت القطر الرئيسي تساوي صفر ، أي المصفوفة المثلثة لها الشكل

T=(a11a12...a1n0a22...a2n............00...ann)


يوجد أدناه رمز الوظيفة الذي يحول المصفوفة الأصلية إلى مصفوفة مثلثة. ولكن في وظيفتنا ، سنعمل مع مصفوفة مستطيلة ، أي أنها قد لا تكون مربعة. يمكن للقارئ بسهولة تعديل رمز الوظيفة بحيث يرجع مصفوفة مثلثة مربعة باستخدام الوظيفة التي فحصناها سابقًا.

static member T matrix =
    let values = matrix.values |> Array2D.mapi (fun x y v -> if y < x then 0 else v)
    { values = values }

تحوّل الدالة Array2D.mapi الصفيف ثنائي الأبعاد الأصلي إلى صفيف جديد باستخدام معالج يأخذ ثلاث معلمات رقم الصف

x رقم العمود
y العمود
الخامس محتويات الخلية

if y < x then 0 else v

هنا نتحقق مما إذا كان العنصر أسفل القطر الرئيسي وإذا كان الأمر كذلك ، فاملأ الخلية 0. وإلا ، فإن القيمة الأولية من مصفوفة الإدخال.

فيما يلي مثال على استخدام هذه الوظيفة.

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R = Matrix.triangular A
printfn "origin = \n %A" A.values
printfn "triangular = \n %A" R.values

نحصل على النتيجة التالية

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
triangular = 
 [[1; 2; 3]
 [0; 5; 6]
 [0; 0; 9]
 [0; 0; 0]]

تسمى المصفوفة المربعة قطريًا إذا كانت جميع عناصرها الموجودة خارج القطر الرئيسي تساوي الصفر


static member D matrix =
    let diagonal = matrix.values |> Array2D.mapi (fun x y v -> if x <> y then 0 else v)
    { values = diagonal }

هذه الوظيفة تشبه إلى حد كبير الوظيفة السابقة ، فقط شرط التحقق مختلف. فيما يلي مثال للاستخدام

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R = Matrix.D A
printfn "origin = \n %A" A.values
printfn "diagonal = \n %A" R.values

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
diagonal = 
 [[1; 0; 0]
 [0; 5; 0]
 [0; 0; 9]
 [0; 0; 0]]

المصفوفة القطرية هي وحدة ويشار إليها بالرمز E إذا كانت جميع عناصرها الموجودة على القطر الرئيسي تساوي الوحدة

E=(10...001...0............00...1)


تنفيذ مثل هذه المصفوفة على F # يبدو هكذا

static member E rows cols =
    let array2d = Array2D.init rows cols (fun x y -> if x = y then 1 else 0)
    { values = array2d }

عمليات المصفوفة مع F #


يمكن تنفيذ عدد من الإجراءات على المصفوفات ، وكذلك على الأرقام ، وبعضها مشابه للعمليات على الأرقام ، وبعضها محدد.
مجموع المصفوفتين Amn = (aij) و Bmn = (bij) من نفس الحجم هو مصفوفة من نفس الحجم A + B = Cmn = (cij) ، والتي تساوي عناصرها مجموع عناصر المصفوفات A و B الموجودة في الأماكن المقابلة

cij=aij+bij,i=1,2,...,m,j=1,2,...,n


على سبيل المثال ، بالنسبة للمصفوفتين A و B ، نجد المجموع A + B

A=(231506),B=(331720),A+B=(162226)


خذ بعين الاعتبار الرمز لإضافة مصفوفتين

static member (+) (matrix1, matrix2) =
    if Matrix.isEquallySized matrix1 matrix2 then
        let array2d = matrix1.values |> Array2D.mapi (fun x y v -> matrix2.values.[x, y] + v)
        { values = array2d }
    else failwith "matrix1 is not equal to matrix2"

قبل إضافة المصفوفات ، تحتاج إلى التأكد من أن أبعادها تتزامن ، وإلا فإن الوظيفة تستثني. فيما يلي مثال على استخدام هذه الوظيفة

let a = array2D [[2;3]
                 [1;-5]
                 [0;6]]
let A = Matrix.ofArray2D a

let b = array2D [[-3;3]
                 [1;7]
                 [2;0]]
let B = Matrix.ofArray2D b

let R = A+B
printfn "A+B =\n %A" R.values

A+B =
 [[-1; 6]
 [2; 2]
 [2; 6]]

ناتج المصفوفة A = (aij) بالرقم k هو المصفوفة kA = (kaij) من نفس حجم المصفوفة A التي تم الحصول عليها عن طريق ضرب جميع عناصر المصفوفة A في الرقم k

سبيل المثال، لإعطاء مصفوفة A نجد مصفوفة 3A

A=(230154),3A=(69031512)



static member (*) (value, matrix) = 
    let array2d = matrix.values |> Array2D.mapi (fun _ _ v -> v * value)
    { values = array2d }

مصفوفة -A = (- 1) * A وسوف يطلق على العكس مصفوفة A . من هذا التعريف ، ننتقل بسلاسة إلى التالي
الفرق بين المصفوفات A و B ذات الأحجام المتساوية هو مجموع المصفوفة A والمصفوفة المقابلة لـ B

static member (-) (matrix1: Matrix, matrix2: Matrix) = 
    if Matrix.isEquallySized matrix1 matrix2 then
        matrix1 + (-1)*matrix2
    else failwith "matrix1 is not equal to matrix2"

تسمى مصفوفتان متسقة إذا كان عدد أعمدة الأول يساوي عدد صفوف الثاني

A=(2103),B=(05211437)



static member isMatched matrix1 matrix2 = 
    let row1Count = matrix1.values.[0,*].Length
    let col2Count = matrix2.values.[*,0].Length

    row1Count = col2Count

مطلوب التحقق من اتساق المصفوفة لمضاعفتهم.
المصفوفة المتماسكة AB للمنتج Amn = (aij) و Bnp = (bjk) هي المصفوفة Cmn = (cik) ، يتم احتساب العنصر cik كمجموع الصفوف i -th من المصفوفة A والعناصر المقابلة في العمود k من المصفوفة B

احسب منتج المصفوفات

A=(102310),B=(105120)


قرار تحديد منتج المصفوفات

AB=(1(1)+05+2(2)10+01+203(1)+15+0(2)30+11+00)=(5021)


ضع في اعتبارك كود ضرب مصفوفتين

static member (*) (matrix1, (matrix2: Matrix)) =
    if Matrix.isMatched matrix1 matrix2 then
        let row1Count = matrix1.values.[*,0].Length
        let col2Count = matrix2.values.[0,*].Length

        let values = Array2D.zeroCreate row1Count col2Count

        for r in 0..row1Count-1 do
            for c in 0..col2Count-1 do
                let row = Array.toList matrix1.values.[r,*]
                let col = Array.toList matrix2.values.[*,c]

                let cell = List.fold2 (fun acc val1 val2 -> acc + (val1 * val2)) 0 row col
                values.[r,c] <- cell

        { values = values }

    else failwith "matrix1 is not matched to matrix2"

دعونا نلقي نظرة على الرمز بمزيد من التفصيل.
قبل الضرب ، عليك التأكد من أن المصفوفات متناسقة

if Matrix.isMatched matrix1 matrix2 then

المصفوفة الناتجة سيكون لها بعد حيث يكون عدد الصفوف هو نفسه المصفوفة الأولى وعدد الأعمدة هو نفس المصفوفة الثانية

let row1Count = matrix1.values.[*,0].Length
let col2Count = matrix2.values.[0,*].Length

//        
let values = Array2D.zeroCreate row1Count col2Count

بعد ذلك ، ننتقل عبر جميع الصفوف وجميع أعمدة المصفوفات الأصلية

for r in 0..row1Count-1 do
    for c in 0..col2Count-1 do
        let row = Array.toList matrix1.values.[r,*]
        let col = Array.toList matrix2.values.[*,c]

نحسب القيمة الإجمالية لكل خلية

let cell = List.fold2 (fun acc val1 val2 -> acc + (val1 * val2)) 0 row col

تتلقى الدالة List.fold2 قائمتين عند الإدخال (الصف والعمود) وتمرر المعلمات التالية إلى المعالج

acc - المجمع الذي يحتوي على نتيجة الحساب السابق
1 - محتويات الخلية من الصفيف الأول. في حالتنا ، هذا هو الصف من المصفوفة الأولى
val2 - محتويات الخلية من المصفوفة الثانية ، أي أعمدة المصفوفة الثانية.

بما أن المصفوفات متناسقة ، فنحن على يقين من أننا لن نتجاوز الصفائف.

يضيف المعالج إلى المركم منتج خلايا من الصفوف والعمود ، وسيتم تمرير القيمة الناتجة إلى التكرار التالي. وبالتالي ، فإن النتيجة النهائية للدالة List.fold2ستكون القيمة النهائية لمنتجات مصفوفتين. يبقى فقط لملئها بالمصفوفة الفارغة التي تم إنشاؤها مسبقًا

values.[r,c] <- cell

الذي سيعود نتيجة لذلك

{ values = values }

فيما يلي مثال على استخدام هذه الوظيفة

let a = array2D [[1;0;2]
                 [3;1;0]]
let A = Matrix.ofArray2D a

let b = array2D [[-1;0]
                 [5;1]
                 [-2;0]]
let B = Matrix.ofArray2D b

let R = A*B

printfn "A*B =\n %A" R.values

A1*B1 =
 [[-5; 0]
 [2; 1]]

إذا كانت k ∈ N ، فإن القوة kth للمصفوفة المربعة A هي نتاج المصفوفات k

Ak=AA...A(k)


ضع في اعتبارك الرمز على F # لمنتج مصفوفة إلى قوة. سيتم استخدام عائد الذيل هنا حتى لا يتم تجاوز المكدس بقوة كبيرة. عودية الذيل هي عودية يحولها المترجم في النهاية إلى حلقة. إذا كان ذلك ممكنًا ، فمن المستحسن أن تستخدم دائمًا العود الذيل بدلاً من المعتاد ، ولكن لهذا تحتاج إلى كل إطار عائد لإرجاع القيمة المحسوبة النهائية. تسمى هذه القيمة عادةً المركم ويتم تمريرها إلى إطار العودية التالي. هذا ، على عكس العودية المنتظمة ، التي تُرجع القيمة المحسوبة في المكدس ، يعيد العائد الذيل القيمة المحسوبة إلى أسفل المكدس. يقوم كل إطار جديد للإعادة بحساباته الخاصة ويضيفها إلى القيمة المحسوبة سابقًا ، والتي يتم تخزينها في البطارية. بعد ذلك،بما أن الإطار الأخير من العودية يعمل ، فإن للمراكم بالفعل قيمة محسوبة ، والتي تعود ببساطة نتيجة لذلك.

وبالتالي ، يمكن للمترجم تحسين الكود وتحويله إلى حلقة عادية.


//    
// matrix -  
// value -  
static member (^^) (matrix, value) =

    //  ,    
    // m - 
    // p =  
    let inRecPow m p =

        //  
        // acc -  .   Matrix
        // p -     
        //         
        let rec recPow acc p =
            //   
            match p with
            | x when x > 0 ->
                //    
                //      ,      
                let nextAcc = acc*m
                //           
                recPow nextAcc (x-1)
            //    ,    
            | _ -> acc

        //   ,         
        let dim = Matrix.sizes matrix
        let colCount = snd dim
        let rowCount = fst dim

        let u = Matrix.E rowCount colCount
        //           
        recPow u p

    //  ,      
    let powMatrix = inRecPow matrix value
    //   
    { values = powMatrix.values }

يحتوي الرمز على تعليقات تفصيلية حول كيفية عمله. يتطلب شرحا قليلا ، لماذا يتم استخدام مصفوفة الوحدة؟ وهو ضروري للإطار الأول من العودية ويعمل كقيمة أساسية للمركم ، حيث سيتم تجميع النتيجة النهائية.
فيما يلي مثال على استخدام وظيفتنا

A=(1021)


A2=AA=(1021)(1021)=(1001)


A3=AA2=(1021)(1001)=(1021)


نحن نحسب المنتج التالي

f(A)=2A34A2+3E


حيث E هي مصفوفة الهوية. نظرًا لأنه لا يمكننا إضافة رقم إلى المصفوفة ، يجب أن نضيف 3E .

2(1021)4(1001)+3(1001)=(1043)



//     
static member (+) (matrix, (value: int)) =
    let dim = Matrix.sizes matrix
    let r = fst dim
    let c = snd dim

    //   
    let unit = Matrix.E r c
    //          
    value*unit + matrix

let a = array2D [[1;0]
                 [2;-1]]
let A = Matrix.ofArray2D a

let R = 2*(A^^3) - 4*(A^^2) + 3
printfn "2*A^3 - 4*A^2 + 3 =\n %A" R.values

2*A5^3 - 4*A5^2 + 3 =
 [[1; 0]
 [4; -3]]

المصفوفة A T التي تتكون أعمدتها من صفوف المصفوفة A مع نفس الأرقام ونفس تسلسل العناصر تسمى المنقولة إلى المصفوفة A

static member transpose matrix =
    let dim = Matrix.sizes matrix
    let rows = fst dim
    let cols = snd dim

    //      
    let tMatrix = Matrix.O cols rows
    //       
    matrix.values |> Array2D.iteri(fun x y v -> tMatrix.values.[y, x] <- v)

    //  
    tMatrix

مثال للاستخدام

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R6 = Matrix.T A
printfn "origin = \n %A" A.values
printfn "transpose = \n %A" R.values

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
transpose = 
 [[1; 4; 7; 10]
 [2; 5; 8; 11]
 [3; 6; 9; 12]]

ملخص


في هذه المقالة ، درسنا أمثلة على تنفيذ واستخدام المصفوفات من نظرية الجبر الخطي. وكذلك العمليات الحسابية الأساسية عليها ، باستخدام نهج وظيفي في F #. آمل أن يتمكن القارئ من تقدير المرونة التي توفرها اللغات الوظيفية.

الكود المصدر الكامل لوحدة المصفوفة ، التي تم النظر في أجزاء منها في إطار المقالة ، يمكنك العثور عليها على جيثب.

جيثب ماتريكس

All Articles