На самом деле, помощь понадобилась четверокурсникам. Они уже давно забыли, как решать системы линейных уравнений, да и не заставишь их (в том числе меня). Но что поделаешь, если преподавателю по численным методам захотелось народ помучить? Что касается меня, меня решать что-то уже не заставишь, мне проще написать программу, которая делает это автоматически. Собственно, я и написал программу, которая решает линейную систему по формулам крамера, выводя все сделанные выкладки в TeX, при этом определитель находится не методом Гаусса, а "наивным" методом, как обычно и делают в институте. Собственно, это первое (размером более 50 строк), что я написал на Хаскелле. Прошу оценить и помочь советом, что делается по-другому. Собственно, сам код (компилится последним GHC с опциями -XMultiParamTypeClasses -XTypeSynonymInstances, причём вторую опцию поставил по интуиции, зачем она нужна, толком не понял):
import qualified Array
import Data.Ratio
import Data.Ix
-------------------
-- StringBuilder
--infixl 0 :++
data StringBuilder = SB String | StringBuilder :++ StringBuilder
buildString :: StringBuilder -> String
buildString builder =
let
build' (SB content) acc = content ++ acc
build' (l :++ r) acc = build' l (build' r acc)
in
build' builder []
emptyBuilder = SB []
join :: StringBuilder -> [StringBuilder] -> StringBuilder
join sep [] = emptyBuilder
join sep (h:t) = h :++ foldr (\e -> \acc -> sep :++ e :++ acc) emptyBuilder t
-------------------
-- Type classesinfix 9 !
class (Ix i) => Indiced t i c where
(!) :: t -> i -> c
class ShowTex t where
showTex :: t -> StringBuilder
-------------------
-- Matrixtype MatrixIndex = (Int, Int)
data Matrix = Matrix (Array.Array MatrixIndex Rational)
instance Indiced Matrix MatrixIndex Rational where
(Matrix content) ! index = content Array.! index
mkMatrix :: Int -> [((Int, Int), Rational)] -> Matrix
mkMatrix size content = Matrix (Array.array ((1, 1), (size, size)) content)
(//) :: Matrix -> [((Int, Int), Rational)] -> Matrix
(Matrix content) // newContent = Matrix (content Array.// newContent)
matrixSize :: Matrix -> Int
matrixSize (Matrix content) = let ((_, _), (size, _)) = Array.bounds content in size
instance ShowTex Matrix where
showTex matrix =
let
size = matrixSize matrix
rowToTex :: Int -> StringBuilder
rowToTex row = join (SB "&") [showTex ((matrix!(row, i :: Int)) :: Rational) | i <- [1..size]]
in
SB "\\begin{array}{" :++ (SB . take size . repeat) 'c' :++ SB "}" :++
join (SB "\\\\") [rowToTex i | i <- [1..size]] :++
SB "\\end{array}"instance ShowTex Rational where
showTex value =
let
denom = abs (denominator value)
numer = abs (numerator value)
absTex =
if denom == 1 then
SB (show numer)
else
SB "\\frac{" :++ SB (show numer) :++ SB "}{" :++ SB (show denom) :++ SB "}"in
if value < 0 then SB "(-" :++ absTex :++ SB ")"else absTex
simpleMatrix :: Int -> [[Rational]] -> Matrix
simpleMatrix size content = mkMatrix size
(foldr (++) [] [extractRow row rowIndex | (row, rowIndex) <- zip content [1..size]])
where
extractRow :: [Rational] -> Int -> [((Int, Int), Rational)]
extractRow row rowIndex = foldr (:) []
[((rowIndex, colIndex), v) | (v, colIndex) <- zip row [1..size]]
minor :: (Int, Int) -> Matrix -> Matrix
minor (row, col) matrix =
let
size = matrixSize matrix
fixIndices r c = (if r >= row then r + 1 else r, if c >= col then c + 1 else c)
in
mkMatrix (size - 1) [((row, col), matrix!(fixIndices row col)) | row <- [1..size-1], col <- [1..size-1]]
-------------------
-- Vectordata Vector = Vector (Array.Array Int Rational)
mkVector :: Int -> [(Int, Rational)] -> Vector
mkVector size content = Vector (Array.array (1, size) content)
updateVector :: Vector -> [(Int, Rational)] -> Vector
updateVector (Vector content) newContent = Vector (content Array.// newContent)
vectorSize :: Vector -> Int
vectorSize (Vector content) = let (_, size) = Array.bounds content in size
instance Indiced Vector Int Rational where
(Vector content) ! index = content Array.! index
instance ShowTex Vector where
showTex vector =
let
size = vectorSize vector
in
SB "\\begin{array}{c}" :++
join (SB "\\\\") [showTex ((vector!(i)) :: Rational) | i <- [1..size]] :++
SB "\\end{array}"-------------------
-- Utilities
splitString :: String -> [String]
splitString s =
let
split' (h:t) =
let
(p:q) = split' t
in
if h == ' ' || h == '\r' || h == '\n'then
if null p then p : q else [] : p : q
else
(h : p) : q
split' [] = [[]]
in
split' s
readIntegers :: String -> [Int]
readIntegers = map read . splitString
readExtMatrix :: String -> (Matrix, Vector)
readExtMatrix text =
let
(size : content) = readIntegers text
indices = [(r, c) | r <- [1..size], c <- [1..size]]
vectorContent = drop (size * size) content
in
(mkMatrix size (zip indices [(toInteger x) % 1 | x <- content]),
mkVector size (zip [1..size] [(toInteger x) % 1 | x <- vectorContent]))
makeVarVectorTex :: StringBuilder -> Int -> StringBuilder
makeVarVectorTex var size =
SB "\\left(\\begin{array}{c}" :++
join (SB "\\\\") [var :++ SB "_" :++ SB (show i) | i <- [1..size]] :++
SB "\\end{array}\\right)"
replaceColumn :: Int -> Vector -> Matrix -> Matrix
replaceColumn index v m = m // [((i, index), (v!i) :: Rational) | i <- [1..matrixSize m]]
-------------------
-- Solvingdata Solution a = Solution StringBuilder a
determ :: Matrix -> Solution Rational
determ matrix =
let
size = matrixSize matrix
in
case size of
1 ->
Solution emptyBuilder (matrix!(1 :: Int, 1 :: Int))
2 ->
let
value =
matrix!(1 :: Int, 1 :: Int) * matrix!(2 :: Int, 2 :: Int) -
matrix!(2 :: Int, 1 :: Int) * matrix!(1 :: Int, 2 :: Int)
builder' =
SB "$$\\left|" :++ showTex matrix :++ SB "\\right| = " :++
showTex ((matrix!(1 :: Int, 1 :: Int)) :: Rational) :++ SB " \\cdot " :++
showTex ((matrix!(2 :: Int, 2 :: Int)) :: Rational) :++ SB " - " :++
showTex ((matrix!(1 :: Int, 2 :: Int)) :: Rational) :++ SB " \\cdot " :++
showTex ((matrix!(2 :: Int, 1 :: Int)) :: Rational) :++ SB " = " :++
showTex value :++ SB "$$\r"in
Solution builder' value
n ->
let
addSolution index (solutions, builder) =
let sol@(Solution builder' _) = determ (minor (1, index) matrix)
in (sol : solutions, builder' :++ builder)
(solutions', builder) = foldr addSolution ([], emptyBuilder) [1..n]
solutions = reverse solutions'
addResult (Solution _ v, index) acc =
acc + (if index `mod` 2 == 0 then -1 else 1) * v * matrix!(1 :: Int, index :: Int)
result = foldr addResult 0 (zip solutions [1..n])
appendMinor index builder =
let
v = (matrix!(1 :: Int, index :: Int)) :: Rational
minorTex = showTex (minor(1, index) matrix)
signTex = if index == 1 then SB ""else if index `mod` 2 == 0 then SB "-"else SB "+"in
signTex :++ showTex v :++ SB "\\cdot\\left|" :++ minorTex :++ SB "\\right|" :++ builder
appendMinor' (Solution _ m, index) builder =
let
v = (matrix!(1 :: Int, index :: Int)) :: Rational
minorTex = showTex m
signTex = if index == 1 then SB ""else if index `mod` 2 == 0 then SB " - "else SB " + "in
signTex :++ showTex v :++ SB " \\cdot " :++ minorTex :++ builder
builder' =
builder :++
SB "$$\\left|" :++ showTex matrix :++ SB "\\right| = " :++
foldr appendMinor emptyBuilder [1..n] :++ SB " = " :++
foldr appendMinor' emptyBuilder (zip solutions' [1..n]) :++ SB " = "in
Solution (builder' :++ showTex result :++ SB "$$\r") result
kramerSolve :: (Matrix, Vector) -> Solution Vector
kramerSolve (m, v) =
let
size = matrixSize m
task =
SB "$$\\left(" :++ showTex m :++ SB "\\right)" :++ makeVarVectorTex (SB "x") size :++
SB " = \\left(" :++ showTex v :++ SB "\\right)$$\r"
makeBindingTex var matrix det =
SB "$$" :++ var :++ SB " = \\left|" :++ showTex matrix :++
SB "\\right| = " :++ showTex det :++ SB "$$\r"
makeIndexBindingTex var index matrix det =
makeBindingTex (var :++ SB "_" :++ SB (show index)) matrix det
(Solution prologue det) = determ m
matrices = [replaceColumn i v m | i <- [1..size]]
solutions = [determ x | x <- matrices]
prologue' =
makeBindingTex (SB "\\Delta") m det :++
join (SB "") [s :++ makeIndexBindingTex (SB "\\Delta") i m v | ((Solution s v), m, i) <- zip3 solutions matrices [1..size]]
resultList = [d / det | (Solution _ d) <- solutions]
result = mkVector size (zip [1..size] resultList)
epilogue =
SB "$$" :++ makeVarVectorTex (SB "x") size :++
SB " = \\left(" :++ showTex result :++ SB "\\right)$$\r"in
Solution (task :++ prologue :++ prologue' :++ epilogue) result
-------------------
-- Main
main = do
input <- getContents
m <- do return (readExtMatrix input)
putStrLn (let (Solution b _) = kramerSolve m in buildString b)
Меня одолевают смутные сомнения, что в случае со StringBuilder я изобрёл велосипед, но когда мне там разбираться в неудобной справке GHC? Кроме того, я уверен, что существуют готовые модули для работы с линейной алгеброй, однако, как мне кажется, от них мало толку, так как нужно не просто получить ответ, а расписать выкладки.
... << RSDN@Home 1.2.0 alpha rev. 672>>
Re: [Haskell] Первые опыты / В помощь первокурсникам
Вопрос чуть "в сторону" — ты считаешь, что комментарии в хаскельном коде излишли?
И почему именно ТеХ? И тебе не кажется, что смешивать вычисления и формирование "выходного" теха несколько запутывает логику?
Ну а про размер функций курсе на первом вроде пытаются внушить, что портянки — зло
P.S. Если честно сильно в код не вчитывался, да и в Хаскеле я далеко не гуру, просто вот субъективные впечатления
Re[2]: [Haskell] Первые опыты / В помощь первокурсникам
Здравствуйте, Курилка, Вы писали:
К>Вопрос чуть "в сторону" — ты считаешь, что комментарии в хаскельном коде излишли?
Гм, конечно нет. Но тут кода всего строк 200. Не думаю, что тут есть, что комментировать.
К>И почему именно ТеХ?
А что же ещё?
К>И тебе не кажется, что смешивать вычисления и формирование "выходного" теха несколько запутывает логику?
Кажется. Но тут задача — вывести все выкладки. Так что ничего не поделаешь.
К>Ну а про размер функций курсе на первом вроде пытаются внушить, что портянки — зло
Не понял. Это про kramerSolve и determ? Но они же формируют вывод в TeX. Там как раз на это и уходит основной объём кода. Не понимаю, как тут что-то ужать?
... << RSDN@Home 1.2.0 alpha rev. 672>>
Re[3]: [Haskell] Первые опыты / В помощь первокурсникам
Здравствуйте, konsoletyper, Вы писали:
K>Здравствуйте, Курилка, Вы писали:
К>>И тебе не кажется, что смешивать вычисления и формирование "выходного" теха несколько запутывает логику?
K>Кажется. Но тут задача — вывести все выкладки. Так что ничего не поделаешь.
Поделаешь-поделаешь
Древние были правы, когда говорили "разделяй и властвуй"
К>>Ну а про размер функций курсе на первом вроде пытаются внушить, что портянки — зло
K>Не понял. Это про kramerSolve и determ? Но они же формируют вывод в TeX. Там как раз на это и уходит основной объём кода. Не понимаю, как тут что-то ужать?
Ну реально для прочтения этого уже требуется по-моему несколько напрягаться, ощущение, что ты имеративный код записываешь через эти :++, возможно, это всё получится в монаду завернуть, но чтот, если честно, хочется оставить удовольствие тебе
Re[4]: [Haskell] Первые опыты / В помощь первокурсникам
Здравствуйте, Курилка, Вы писали:
К>Ну реально для прочтения этого уже требуется по-моему несколько напрягаться, ощущение, что ты имеративный код записываешь через эти :++, возможно, это всё получится в монаду завернуть, но чтот, если честно, хочется оставить удовольствие тебе
:++ — это не императивщина, это быстрый аналог ++.
... << RSDN@Home 1.2.0 alpha rev. 672>>
Re[5]: [Haskell] Первые опыты / В помощь первокурсникам
От:
Аноним
Дата:
28.05.08 17:39
Оценка:
K>:++ — это не императивщина, это быстрый аналог ++.
Э-э-э... А почему ты думаешь, что он будет сильно быстрее?
Re[6]: [Haskell] Первые опыты / В помощь первокурсникам
Здравствуйте, http://migmit.vox.com/, Вы писали:
HMV>Э-э-э... А почему ты думаешь, что он будет сильно быстрее?
А потому что ++ требует столько действий, сколько элементов в левом списке. Поэтому идеальный случай — когда каждый раз списки добавляются слева. В произвольном же случае всё будет работать довольно долго. :++ — это просто конструктор StringBuilder. Он срабатывает моментально. А buildString обходт полученное дерево справа налево, так что ++ будет всегда добавлять списки слева, поэтому он отработает за n операций, где n — длина получившейся строки.
... << RSDN@Home 1.2.0 alpha rev. 672>>
Re[5]: [Haskell] Первые опыты / В помощь первокурсникам
Здравствуйте, konsoletyper, Вы писали:
K>Здравствуйте, Курилка, Вы писали:
К>>Ну реально для прочтения этого уже требуется по-моему несколько напрягаться, ощущение, что ты имеративный код записываешь через эти :++, возможно, это всё получится в монаду завернуть, но чтот, если честно, хочется оставить удовольствие тебе
K>:++ — это не императивщина, это быстрый аналог ++.
Т.е. для тебя толпа :++ очень принципиально отличается от толпы >>= ?
Ну хорошо, раз так
Re[7]: [Haskell] Первые опыты / В помощь первокурсникам
Здравствуйте, konsoletyper, Вы писали:
K>Здравствуйте, http://migmit.vox.com/, Вы писали:
HMV>>Э-э-э... А почему ты думаешь, что он будет сильно быстрее?
K>А потому что ++ требует столько действий, сколько элементов в левом списке. Поэтому идеальный случай — когда каждый раз списки добавляются слева. В произвольном же случае всё будет работать довольно долго. :++ — это просто конструктор StringBuilder. Он срабатывает моментально. А buildString обходт полученное дерево справа налево, так что ++ будет всегда добавлять списки слева, поэтому он отработает за n операций, где n — длина получившейся строки.
Ты хоть сам понимаешь, что :++ вызовет ровно столько же действий, поскольку всё равно будет собран при помощи buildString? И учти ленивость языка: (++) НЕ будет выполнен, пока не потребуется, а будет сохранён как thunk.
По теме.
Решил пользоваться MultiParamTypeClasses — выучи ещё и FunctionalDependencies. В данном случае достаточно прописать "class (Ix i) => Indiced t i c | t -> i c", чтобы зубодробительные вещи типа ((matrix!(1 :: Int, 1 :: Int)) :: Rational) сократились просто до matrix!(1,1).
Обобщать, обобщать, и ещё раз обобщать! Введя функции типа, скажем, texBrackets c1 c2 s = "\\left" ++ c1 : s ++ "\\right" ++ [c2] и её частные случаи roundBrackets = texBrackets '(' ')' и barBrackets = texBrackets '|' '|', ты сделаешь код куда как понятнее. Хороша также функция
— многое становится проще. Сюда же: функция, обрамляющая аргумент в "$$".
Реализация Matrix, ИМХО, страдает от многочисленных копирований. Подумай о таком варианте: data Matrix = Matrix (Array.Array MatrixIndex Rational) (Array.Array Int Int) (Array.Array Int Int), с косвенным доступом Matrix content rows cols ! (i,j) = content Array.! (rows ! i, cols ! j). Преимущество в том, что для взятия минора тебе будет достаточно удалить один элемент из rows и один из cols. Может быть, имеет смысл даже хранить их не как массивы, а как списки или зипперы. Кроме того, выкинь (//) — эта функция используется один раз, и не там, где надо. При таком подходе тебе надо будет хранить всю расширенную матрицу, а список matrices будет получаться из неё заменой списка столбцов (которые будут при этом идти не совсем по порядку).
let буква = выражение in case буква of — легко заменяется на case выражение of. И читается гораздо проще.
Стилистическое замечание: я бы поменял порядок полей в Solution. Это сделает возможным вместо let builder = что-то-длинное in Solution builder value писать Solution value $ что-то-длинное.
Читай справку по стандартной библиотеке. В частности, replicate из Data.List — это ровно то, что у тебя делается комбинацией take и repeat. join sep ss = concat $ intersperse sep ss. Функция main отлично пишется в одну строчку при помощи interact.
Думай, что пишешь. foldr (++) [] — это concat, foldr (:) [] — писать вообще не надо, это тождественная функция. В частности, определение simpleMatrix сокращается до
m <- return что-то-там — сокращается до let m = что-то-там, а потом вообще выкидывается, поскольку в дальнейшем m встречается только один раз и вполне можно написать вместо него что-то-там.
Подумай о том, чтобы дать своим Solution-ам инстанс класса Num. С тем, чтобы ОДНОВРЕМЕННО производить вычисления со значениями, и в то же время комбинировать TeX-овские строки соответствующим образом. Те методы класса, которые тебе не нужны, можно не реализовывать.
200 строчек Haskell-а — это до фигищи. Комментарии ОБЯЗАТЕЛЬНЫ!
Re[8]: [Haskell] Первые опыты / В помощь первокурсникам
Здравствуйте, http://migmit.vox.com/, Вы писали:
HMV>Ты хоть сам понимаешь, что :++ вызовет ровно столько же действий, поскольку всё равно будет собран при помощи buildString? И учти ленивость языка: (++) НЕ будет выполнен, пока не потребуется, а будет сохранён как thunk.
Собственно, да. Только вот меня терзают смутные сомнения: тут дело не в ленивости, а в deforestation. Ленивый случай от энергичного будет отличаться тем, что будет куча заворачиваний/разворачиваний из списка/в список одиних и тех же пар элементов.
По поводу thunk'а — мне казалось, что они порождаются после редукций, а не до.
HMV>По теме.
[вырезано]
Вот это мне и надо было. Единственный момент — я хотел так же добавить метод Гаусса, потому // всё же понадобится, а матрицы придётся всё-таки представлять в виде массивов.
HMV>200 строчек Haskell-а — это до фигищи. Комментарии ОБЯЗАТЕЛЬНЫ!
Ладно, сделаю.
... << RSDN@Home 1.2.0 alpha rev. 672>>
Re: [Haskell] Первые опыты / В помощь первокурсникам
1. {-# OPTIONS -XMultiParamTypeClasses -XTypeSynonymInstances #-} в начало файла поможет
2. StringBuilder для производительности? Возможно, подойдёт Data.Sequence, ByteString, Rope-ByteString и т.д.
3. Личное предпочтение: where лучше, чем let/in при определении функции — более декларативно, существенное вперёд.
4. join — известная монадическая функция, называть так свою я бы не стал. То же касается операции (!), например.
5. Типы данных с одним конструктором вокруг одного значения (Martxix) можно делать newtype, помимо производительности мы можем ещё и легко выводить инстансы обёрнутого типа.
12. Постоянная работа с переводом типов туда-обратно. toInteger, явное указание типа и т.д. К сожалению, библиотека Haskell в этом отношении не очень продумана, а может быть дело связано с производительностью. Но, на данном этапе, если мы хотим избавиться от Int/Integer в пользу более общего Integral приходится использовать, например, genericDrop. Не очень, согласен.
13. Выражения типа [f x | x <- xs] лучше читаются как map f xs.
14. Ну, и чтобы кол-во пунктов не было равно 13, simpleMatrix проще записать как
simpleMatrix size content = mkMatrix size $ zip (,) coords (concat content)
where
coords = [(i,j)| i <- [1..size], j <- [1..size]]
хотя coords я бы записал через liftM2 (,) уж очень известная идиома и не нужны эти глупые i и j.
Удачи!
Re[9]: [Haskell] Первые опыты / В помощь первокурсникам
От:
Аноним
Дата:
28.05.08 21:14
Оценка:
HMV>>Ты хоть сам понимаешь, что :++ вызовет ровно столько же действий, поскольку всё равно будет собран при помощи buildString? И учти ленивость языка: (++) НЕ будет выполнен, пока не потребуется, а будет сохранён как thunk.
K>:shuffle: Собственно, да. Только вот меня терзают смутные сомнения: тут дело не в ленивости, а в deforestation. Ленивый случай от энергичного будет отличаться тем, что будет куча заворачиваний/разворачиваний из списка/в список одиних и тех же пар элементов.
K>По поводу thunk'а — мне казалось, что они порождаются после редукций, а не до.
Ы? Ещё разок: результат a ++ b сохраняется как thunk, состоящий из: кода операции (++) и двух списков a и b. Только потом, при, например, печати, он будет вычислен.
HMV>>По теме.
K>[вырезано]
K>:up: Вот это мне и надо было. Единственный момент — я хотел так же добавить метод Гаусса, потому // всё же понадобится, а матрицы придётся всё-таки представлять в виде массивов.
Такой вариант: использовать разные структуры хранения матриц для реализации метода разложения по строке и метода Гаусса; объявить эти структуры инстансами некоего класса с методом determ; весь остальной код остаётся таким же, каким и был, но становится несколько более полиморфным.
Re[2]: [Haskell] Первые опыты / В помощь первокурсникам
L>1. {-# OPTIONS -XMultiParamTypeClasses -XTypeSynonymInstances #-} в начало файла поможет
А ещё лучше {-# LANGUAGE MultiParamTypeClasses, TypeSynonymInstances #-}. И туда же FunctionalDependencies.
L>4. join — известная монадическая функция, называть так свою я бы не стал. То же касается операции (!), например.
Не согласен. Я довольно долго извращался с названиями для нескольких своих функций, называя их join с разными префиксами/суффиксами, потом плюнул, назвал их все join и стал импортировать соответствующие модули квалифицированными.
L>5. Типы данных с одним конструктором вокруг одного значения (Martxix) можно делать newtype, помимо производительности мы можем ещё и легко выводить инстансы обёрнутого типа.
Можно, хотя я как раз предложил использовать тип с более чем одним аргументом у конструктора данных. Так что придётся оставить data.
Вывод инстансов требует GeneralizedNewtypeDeriving в прагму LANGUAGE.
L>8. [extractRow row rowIndex | (row, rowIndex) <- zip content [1..size]] эквивалентно zipWith extractRow content [1..size]
А на самом деле оно там вообще не нужно.
L>11. Вот, кстати, хороший пример, что guards/where декларативнее if/let, если переписать один в один:
L>
А я бы ещё заменил на x `elem` " \r\n".
L>12. Постоянная работа с переводом типов туда-обратно. toInteger, явное указание типа и т.д. К сожалению, библиотека Haskell в этом отношении не очень продумана, а может быть дело связано с производительностью. Но, на данном этапе, если мы хотим избавиться от Int/Integer в пользу более общего Integral приходится использовать, например, genericDrop. Не очень, согласен.
Нет, там проблема элегантно решается FunctionalDependencies.
L>14. Ну, и чтобы кол-во пунктов не было равно 13, simpleMatrix проще записать как
L>
L>simpleMatrix size content = mkMatrix size $ zip (,) coords (concat content)
L> where
L> coords = [(i,j)| i <- [1..size], j <- [1..size]]
L>