| Университет | Университет ИТМО |
| Факультет | Факультет программной инженерии и компьютерной техники (ПИиКТ) |
| Направление | Программная инженерия |
| Дисциплина | Функциональное программирование |
| Студент | Дмитриев Денис Сергеевич |
| Группа | P3312 |
| Преподаватель | Сиразетдинов Азат Ниязович и Голиков Андрей Сергеевич |
| Дата сдачи | 12.11.2025 |
Цель: получить навыки работы с вводом/выводом, потоковой обработкой данных, командной строкой. В рамках лабораторной работы вам предлагается повторно реализовать лабораторную работу по предмету "Вычислительная математика" посвящённую интерполяции (в разные годы это лабораторная работа 3 или 4) со следующими дополнениями:
обязательно должна быть реализована линейная интерполяция (отрезками, link); настройки алгоритма интерполяции и выводимых данных должны задаваться через аргументы командной строки:
какие алгоритмы использовать (в том числе два сразу); частота дискретизации результирующих данных; и т.п.;
входные данные должны задаваться в текстовом формате на подобии ".csv" (к примеру x;y\n или x\ty\n) и подаваться на стандартный ввод, входные данные должны быть отсортированы по возрастанию x; выходные данные должны подаваться на стандартный вывод; программа должна работать в потоковом режиме (пример -- cat | grep 11), это значит, что при запуске программы она должна ожидать получения данных на стандартный ввод, и, по мере получения достаточного количества данных, должна выводить рассчитанные точки в стандартный вывод;
Приложение должно быть организовано следующим образом: +---------------------------+ | обработка входного потока | +---------------------------+ | | поток / список / последовательность точек v +-----------------------+ +------------------------------+ | алгоритм интерполяции |<-----| генератор точек, для которых | +-----------------------+ | необходимо вычислить | | | промежуточные значения | | +------------------------------+ | | поток / список / последовательность рассчитанных точек v +------------------------+ | печать выходных данных | +------------------------+ Потоковый режим для алгоритмов, работающих с группой точек должен работать следующим образом: o o o o o o . . x x x x x x . . o . . x x x x x x . . o . . x x x x x x . . o . . x x x x x x . . o . . x x x x x x . . o . . x x x x x x . . o o o o o o EOF где:
каждая строка -- окно данных, на основании которых производится расчёт алгоритма; строки сменяются по мере поступления в систему новых данных (старые данные удаляются из окна, новые -- добавляются);
o -- рассчитанные данные, можно видеть:
большинство окон используется для расчёта всего одной точки, так как именно в "центре" результат наиболее точен; первое и последнее окно используются для расчёта большого количества точек, так лучших данных для расчёта у нас не будет.
. -- точки, задействованные в рассчете значения o.
x -- точки, расчёт которых для "окон" не требуется.
Пример вычислений (my_lab3 --linear --step 0.7, < -- ввод, > -- вывод): < 0 0 < 1 1
linear: 0 0 linear: 0.7 0.7 < 2 2 linear: 1.4 1.4 3 3 linear: 2.1.4 2.1 linear: 2.8 2.8 < EOF linear: 2.8 2.8 my_lab3 --newton -n 4 --step 0.5 (интерполяция по 4 точкам): < 0 0 < 1 1 < 2 2 3 3 4 4 newton: 0 0 newton: 0.5 0.5 newton: 1 1 newton: 1.5 1.5 newton: 2 2 newton: 2.5 2.5 newton: 3 3 < 5 5 newton: 3.5 3.5 newton: 4 4 < 7 7 newton: 4.5 4.5 newton: 5 5 < 8 8 newton: 5.5 5.5 newton: 6 6 newton: 6.5 6.5 newton: 7 7 < EOF newton: 7.5 newton: 8 Общие требования:
программа должна быть реализована в функциональном стиле; ввод/вывод должен быть отделён от алгоритмов интерполяции; требуется использовать идиоматичный для технологии стиль программирования.
Содержание отчёта:
титульный лист; требования к разработанному ПО, включая описание алгоритма; ключевые элементы реализации с минимальными комментариями; ввод/вывод программы; выводы (отзыв об использованных приёмах программирования).
Общие рекомендации по реализации. Не стоит писать большие и страшные автоматы, управляющие поведением приложения в целом. Если у вас:
Язык с ленью -- используйте лень. Языки с параллельным программированием и акторами -- используйте их. Язык без всей этой прелести -- используйте генераторы/итераторы/и т.п.
module Interpolation.Types
( Point
, Config(..)
, Method(..)
) where
type Point = (Double, Double)
data Method = Linear | Newton Int
deriving (Show, Eq)
data Config = Config
{ method :: Method
, step :: Double
} deriving (Show, Eq)Здесь всё понятно - обрабатываем точки согласно требованиям. В конфиге выбираем метод и шаг. Чтобы подключить два метода можно использовать tee в UNIX. Это сделано специально чтобы разграничить ответственность, чтобы не использовать плохую практику парсинга выхода.
Interpolation.Algo: Вычисляем полиномчики Interpolation.Window: Преобразует ленивый список входных данных в список результатов. Main: Айошечка
process :: Config -> [Point] -> [Point]
process cfg inputStream = go [] inputStream True
where
go window stream isFirst
| length window < winSize =
case stream of
[] -> if length window >= 2 then finalizeWindow window else []
(p:ps) -> go (window ++ [p]) ps isFirst
| otherwise =
let
(start, end) = getRange window isFirst
calculated = [ (x, calcPoint (method cfg) window x)
| x <- takeWhile (<= end) [start, start + step ..] ]
nextWindow = drop 1 window
in
calculated ++ case stream of
[] -> finalizeWindow window
(p:ps) -> go (nextWindow ++ [p]) ps FalseБлагодаря ленивости языка Haskell, вся программа работает как пайплайн. Ввод всего файла в память не происходит — данные запрашиваются по мере необходимости функцией рекурсии.
Линейная интерпол: чек среднее: OK
Линейная интерпол: чек точек: OK
Ньютон интерпол. при n=3:восстановление y=x^2: OK
Окно потока: простой линейный поток: OK
y=x остается y=x для линейной: OK (0.09s)
+++ OK, passed 100 tests.
y=x остается y=x для Ньютона: OK (0.13s)
+++ OK, passed 100 tests; 33 discarded.
Входные данные:
0.0 0.0
1.0 1.0
2.0 4.0
3.0 9.0
4.0 16.0
Выходные:
root@WWamich:/mnt/d/Programming/fp-lab3# stack run -- --method linear --step 0.5 < data.txt
0.0000 0.0000
0.5000 0.5000
1.0000 1.0000
1.5000 2.5000
2.0000 4.0000
2.5000 6.5000
3.0000 9.0000
3.5000 12.5000
4.0000 16.0000
root@WWamich:/mnt/d/Programming/fp-lab3# stack run -- --method newton --n 3 --step 0.5 < data.txt
0.0000 0.0000
0.5000 0.2500
1.0000 1.0000
1.5000 2.2500
2.0000 4.0000
2.5000 6.2500
3.0000 9.0000
3.5000 12.2500
4.0000 16.0000
root@WWamich:/mnt/d/Programming/fp-lab3#
В ходе выполнения лабораторной работы были освоены и применены на практике ключевые концепции функционального программирования:
- Ленивость как инструмент потока это кайф. ленивый ввод getContents + ленивые списки = реализация сложной логики окна фактически декларативно. Избавление от циклов while(!eof). Функция process описывает трансформацию потока данных, а Haskell сам заботится о буферизации и чтении данных из stdin по мере требования результат.
- Property-based тестирование. — проверили основное свойство интерполяции.