Новичок в OCaml: как бы я внедрил метод исключения Гаусса?

Question

Я новичок в OCaml, и я хотел бы использовать метод исключения Гаусса в качестве упражнения. Я легко могу сделать это с помощью алгоритма с сохранением состояния, то есть сохранить матрицу в памяти и рекурсивно работать с ней, передавая ссылку на нее.

Это состояние, однако, попахивает императивным программированием. Я знаю, что в OCaml есть возможности сделать это, но я хотел бы спросить, есть ли какой-нибудь умный функциональный способ, о котором я сначала не думал.

Answer 1

Массивы OCaml являются изменяемыми, и трудно избежать обращения с ними как с массивами на императивном языке.

Haskell имеет неизменяемые массивы, но из моего (ограниченного) опыта работы с Haskell вы в конечном итоге переключаетесь на монадные, изменяемые массивы в большинстве случаев. Неизменяемые массивы, вероятно, удивительны для определенных конкретных целей. Я всегда думал, что вы могли бы написать прекрасную реализацию динамического программирования на Haskell, где зависимости между записями массива полностью определяются выражениями в них. Ключ в том, что вам действительно нужно указывать содержимое каждой записи массива только один раз. Я не думаю, что исключение по Гауссу следует этой схеме, и поэтому кажется, что оно может не подходить для неизменяемых массивов. Однако было бы интересно посмотреть, как это работает.

Answer 2

Вы можете использовать Map для эмуляции матрицы. Ключом будет пара целых чисел, ссылающихся на строку и столбец. Вы захотите использовать собственную функцию get x y, чтобы обеспечить x < n и y < n, вместо того, чтобы обращаться к Map напрямую. (редактировать) Вы можете использовать функцию сравнения в Pervasives напрямую.

module OrderedPairs = struct
    type t = int * int
    let compare = Pervasives.compare
end                     
module Pairs = Map.Make (OrderedPairs)

let get_ n set x y =
    assert( x < n && y < n ); 
    Pairs.find (x,y) set

let set_ n set x y v = 
    assert( x < n && y < n ); 
    Pairs.add (x,y) set v

На самом деле, иметь общий набор функций (get x y и set x y как минимум), без указания реализации, было бы еще лучшим вариантом. Затем функции могут быть переданы в функцию или реализованы в модуле через функтор (лучшее решение, но наличие набора функций, выполняющих только то, что вам нужно, было бы первым шагом, поскольку вы новичок в OCaml). Таким образом, вы можете использовать Map, Array, Hashtbl или набор функций для доступа к файлу на жестком диске для реализации матрицы, если хотите. Это действительно важный аспект функционального программирования; что вы доверяете интерфейсу, а не используете побочные эффекты, и не беспокоитесь о базовой реализации - так как предполагается, что он чистый.

Answer 3

Ответы до сих пор используют / эмулируют изменяемые типы данных, но как выглядит функциональный подход?

Чтобы увидеть, давайте разберем проблему на несколько функциональных компонентов:

GaussianИсключение включает в себя последовательность операций со строками, поэтому сначала полезно определить функцию, которая берет 2 строки и коэффициенты масштабирования и возвращает результирующий результат операции со строкой.

Операции со строками, которые нам нужны, должны исключать переменную (столбец)из определенной строки, поэтому давайте определим функцию, которая берет пару строк и индекс столбца и использует ранее определенную операцию строки, чтобы вернуть измененную строку с нулевой записью этого столбца.

Затем мы определяем две функции,один для преобразования матрицы в треугольную форму, а другой для обратной замены треугольной матрицы в диагональную форму (с использованием ранее определенных функций) путем исключения каждого столбца по очереди.Мы могли бы повторять или рекурсировать по столбцам, и матрица могла бы быть определена как список, вектор или массив списков, векторов или массивов.Входные данные не изменяются, но возвращается измененная матрица, так что мы можем, наконец, сделать:

let out_matrix = to_diagonal (to_triangular in_matrix);

Что делает его функциональным, не является ли данные-типы (массив или список) изменчивы, но как они используются.Этот подход может не быть особенно «умным» или самым эффективным для устранения гауссовских исключений в OCaml, но использование чистых функций позволяет четко выразить алгоритм.