Материалы по запросу: haskell
Функциональное программирование /Росдистант/ Практические задания (Вариант 5-Д,С,Ш)
Тема 3. Типы данных в Haskell Учебные вопросы: 1. Какие основные типы данных существуют в Haskell? 2. Что такое алгебраические типы данных и как они используются в Haskell? 3. Как работают полиморфные
Компьютерное моделирование.фроб_БАК. Синергия. Ответы на ИТОГОВЫЙ ТЕСТ. На отлично!
моделирования. Такие языки как: Fortran, Modula, Pascal, C, Basic относятся к Такие языки как: F#, Haskell, Lisp, Scheme относятся к Что из нижеперечисленного не является языком программирования: … компьютерная
СДО Росдистант Текущий курс Функциональное программирование Практические задания
выбирается из таблицы 1.2. Определить тип вычислительного процесса. Написать программу на языке Haskell. Представить результаты вычислений по заранее подготовленному тесту. Для отладки программы можно
Ответы на тест / РОСДИСТАНТ / Функциональное программирование / 100 вопросов / Промежуточный тест (5 попыток)
Промежуточный тест (Попытка №1) Вопрос 1 Что делает функция “primes” в Haskell: Выберите один ответ: находит все простые числа до заданного числа находит наименьшее простое число, которое
КP «Функциональное и логическое программирование» Haskell "игра пятнашки"
КP «Функциональное и логическое программирование» Haskell "игра пятнашки"
[Росдистант] Технологии и средства конструирования программного обеспечения (тесты, вопросы, ответы)
улучшения читаемости на языках програмирования Выберите один или несколько ответов: Phyton Java Haskell C++ Perl Проектирование по контракту – это Выберите один ответ: установление отношений между классом
Ответы на тест. Мэи. КМ-1. Характеристика и основы программирования ОС Tizen. Набрано 100%. 2199
системах смартфонах смарт-камерах смарт-часах Веб-приложения под ОС Tizen пишутся на языке Haskell Java Rubi JavaScript Python Жест Swipe прокручивает список элементов или при использовании
Росдистант ТГУ. Функциональное программирование. Контрольные мероприятия. Итоговый тест
такое чистые функции в функциональном программировании? Вопрос 26 Что такое тип данных Natural в Haskell: Вопрос 27 Что из следующего является примером монады? Вопрос 28 Что такое чистые функции в функциональном
Интеллектуальные информационные системы
Произведите редукцию выражения. Выберите метод редукции самостоятельно. Разработать программы на языке Haskell: 1. Написать рекурсивную функцию для вычисления и для вывода на экран цифр натурального
Введение в объектно-ориентированное программирование.ои(dor) тест с ответами Синергия/МОИ/ МТИ /МОСАП
*свойства функций 5. Установите соответствия между языками и видами программирования. A. С++ B. 1C C. Haskell D. объектно-ориентированное программирование E. процедурное программирование F. функциональное
Прикладная информатика. Росдистант ТГУ. Промежуточный тест 8. Технологии и средства конструирования программного обеспечения
улучшения читаемости на языках програмирования Выберите один или несколько ответов: Phyton Java Haskell C++ Perl Вопрос 10 Верно Баллов: 1,0 из 1,0 Что включает в себя абстрактный язык? Выберите один ответ:
Прикладная информатика. Росдистант ТГУ. Промежуточный тест. Функциональное программирование
Вопрос 1 Что делает функция primes в Haskell: Выберите один ответ: находит все простые числа до заданного числа находит наименьшее простое число, которое делит заданное число находит произведение всех
Легкие и интересные темы рефератов по информатике: что выбрать студенту в 2025 году
разметки: HTML, XML, JSON — применение и особенности
Функциональное программирование на примере языка Haskell
Принципы объектно-ориентированного программирования
Скриптовые языки и их роль в автоматизации
495 +1
0
Ответы на тесты / РОСДИСТАНТ / Технологии и средства конструирования программного обеспечения / 75 вопросов / Тесты 1-8
улучшения читаемости на языках програмирования Выберите один или несколько ответов: Phyton Java Haskell C++ Perl Вопрос 4 Токен _______ указывает на то, что нужно сделать, но это не исправление
контрольная работа по программированию (оценка "5") университет им. Витте
и интеллектуальные системы" в университете им. Витте. (условия 4 задач приведены в демоверсии; код по HASKELL полностью верный, ответы все верные и взяты из найденной литературы, ничего не выдумано, не придумано
Разберите следующий Haskell-фрагмент и объясните, почему при суммировании большого списка он может вызвать…
Разберите следующий Haskell-фрагмент и объясните, почему при суммировании большого списка он может вызвать переполнение стека/утечку памяти: sum = foldl (+) 0 [1..10000000] — чем это отличается от foldl'
Ответ на вопрос
Коротко: выражение
\(\text{sum} = \text{foldl } (+)\ 0\ [1..10000000]\)
построит длинную цепочку отложенных вычислений (thunks) вида
\((\dots((0+1)+2)+3)\dots +10000000\),
в результате — сильная утечка памяти (и/или переполнение стека при последующей оценке). Строгая версия foldl' не накапливает такие отложенные выражения и работает в постоянной памяти.
Почему так происходит (сжато):
- foldl определён как (упрощённо)
foldl f z (x:xs) = foldl f (f z x) xs.
Но из‑за ленивости Haskell вызов \(f\ z\ x\) не вычисляется сразу — вместо этого накапливается thunk. После n шагов результат выглядит как вложенное невычисленное выражение \((\dots((0+1)+2)+\dots + n)\).
- Когда в конце вы требуете результат (print или evaluate), интерпретатор пытается постепенно раскрывать этот большой thunk. Раскрытие может потребовать большой стек/память и привести к stack overflow или OutOfMemory.
- foldl' (в Data.List) делает строгую оценку аккумулятора на каждом шаге — по сути она делает seq или использует "!" (bang) — поэтому аккумулятор сразу сводится к WHNF, и thunks не накапливаются. Это даёт амортизированную O(1) память.
Как выглядит строгий шаг (упрощённо):
foldl' f acc (x:xs) = let acc' = f acc x in acc' `seq` foldl' f acc' xs
Комментарии о (+) и типах:
- Даже если (+) сам по себе строг в аргументах для Int, это не спасает: если аккумулятор — thunk, то вызов (+) с этим thunk не будет выполнен, если вы его не заставите вычислить. Именно поэтому нужно строго вычислять аккумулятор, а не полагаться на строгость оператора.
Практические тесты и профилирование (рекомендуемые шаги)
1) Минимальные программы
sum_lazy.hs:
import System.IO
main = print (foldl (+) 0 [1..10000000])
sum_strict.hs:
import Data.List (foldl')
main = print (foldl' (+) 0 [1..10000000])
2) Компиляция и запуск с выводом статистики RTS:
ghc -O2 sum_lazy.hs -o sum_lazy
ghc -O2 sum_strict.hs -o sum_strict
./sum_lazy +RTS -s
./sum_strict +RTS -s
Сравните строки "maximum residency", "bytes allocated", "productivity". Ожидаемо: lazy — много аллокаций/большая резидентность или даже крах; strict — мало памяти, быстрая работа.
3) Профайлинг по месту аллокации (heap profile)
ghc -O2 -prof -fprof-auto -rtsopts sum_strict.hs
./sum_strict +RTS -hc -p -RTS
Посмотрите .hp (heap profile) и .prof (time profile) файлы с помощью hp2ps или других инструментов. Это покажет, где происходит распределение памяти и подтверждает, что lazy-версия тратит память на thunks.
4) Отладка в GHCi
- В GHCi можно экспериментировать на меньших списках и смотреть :sprint и контроль evaluate (Control.Exception.evaluate). Это помогает увидеть накопление thunks.
5) Дополнительные тесты
- Повторите тесты для типов Int и Integer (Integer может увеличивать память дополнительно из‑за больших bignum).
- Сравните с Prelude.sum (в разных версиях может быть определён по‑разному) и с реализацией через foldr/scanl.
- Проверьте поведение при компиляции без -O2 (поведение strictness может отличаться).
Выводы кратко:
- foldl накапливает отложенные вычисления — приводит к росту памяти/стеку.
- foldl' заставляет аккумулятор вычисляться немедленно и избегает утечек.
- При численных агрегациях всегда предпочтительна строгая свёртка (foldl' или специализированные функции), либо использовать структуры/алгоритмы, гарантирующие немедленную оценку.
Еще 132
1
Проанализируйте этот фрагмент на Haskell и объясните, что делает код, какие возможности оптимизации предоставляет…
Проанализируйте этот фрагмент на Haskell и объясните, что делает код, какие возможности оптимизации предоставляет ленивость и где она может навредить: fibs = 0 : 1 : zipWith (+) fibs (tail fibs) — сколько
Ответ на вопрос
Кодfibs = 0 : 1 : zipWith (+) fibs (tail fibs)— это классическое ленивое определение бесконечного списка чисел Фибоначчи. Что тут происходит:fibs — список, первый элемент 0, второй 1.zipWith (+) fibs (tail fibs) складывает список с его хвостом поэлементно, поэтому получается последовательность сумм предыдущих двух элементов. Благодаря ленивости список самопорождает: новые элементы вычисляются по мере запроса.Что даёт ленивость (плюсы)Можно оставить бесконечную структуру и брать сколько нужно (streaming): fibs !! 10 вычислит только первые 11 элементов.Шэринг: если несколько мест кода читают один и тот же fibs, ранее вычисленные элементы сохраняются и повторно не пересчитываются — экономия времени.Композиция: удобно конструировать конвейеры вычислений без явного управления памятью.Где ленивость мешает (минусы / подводные камни)Удержание префикса списка (space leak). Если у вас сохраняется ссылка на голову fibs (например, fibs — top-level CAF), то все уже построенные элементы остаются в памяти. При обращении к n-му элементу (fib !! n) будет построена и сохранена вся префиксная часть длины ≈ n — O(n) ячеек памяти.Накопление отложенных вычислений (thunks). Если при наращивании списка значения не принудительно не сворачиваются в нормальное представление, можно накопить большую цепочку thunk'ов и получить рост памяти / стековые проблемы.Размер самих чисел. Для типа Integer числа растут экспоненциально по длине в битах, так что и память на отдельный элемент может быть большой — это отдельный фактор.Сколько памяти требуется для доступа к n-му элементуВ типичном случае при использовании вышеописного top-level fibs и взятии элемента fibs !! n вы аллоцируете примерно n конс-узлов (каждый узел содержит ссылку на значение и ссылку на следующий узел) плюс сами значения (Integer/Int). Итого память ~ O(n) (спайн списка + значения). Для Integer добавляется память на bigint (растёт с n).Если вы не сохраняете ссылку на голову списка и генерация списка используется только для одного последовательного прохода, GC может освободить уже пройденные узлы; тогда максимальная занимаемая память может быть O(1) (потому что старые узлы уже не задействованы). Но при top-level fibs префикс обычно удерживается — значит O(n).Как получить контролируемое использование памятиЕсли вам нужен только n-й элемент и вы не хотите хранить весь префикс, лучше использовать строгий итеративный алгоритм (константная память по длине префикса) или строгую свёртку. Примеры.1) Строгая хвостовая рекурсия (O(n) времени, O(1) памяти):{-# LANGUAGE BangPatterns #-}
fib :: Int -> Integer
fib n = go n 0 1
where
go 0 !a _ = a
go k !a !b = go (k-1) b (a + b)(!-patterns гарантируют, что аккумуляторы не будут оставаться в виде thunk'ов.)2) foldl' вариант:import Data.List (foldl')fib n = fst $ foldl' ((a,b) _ -> (b, a+b)) (0,1) [1..n]Этот вариант тоже O(n) времени, не накапливает thunk'ов благодаря foldl', но создаёт список [1..n] — можно заменить на явный цикл или использовать специализированные итераторы.3) Если нужна ленивость + ограниченное кеширование, можно явным образом кэшировать только окно последних нескольких значений или хранить значения в массиве/vector и при необходимости освобождать старые элементы. Например, построить вектор длины n+1 и затем индексировать:import qualified Data.Vector.Unboxed as VU
buildFibVec :: Int -> VU.Vector Integer
buildFibVec n = VU.create $ do
v <- VU.unsafeNew (n+1)
VU.unsafeWrite v 0 0
when (n >= 1) $ VU.unsafeWrite v 1 1
forM_ [2..n] $ \i -> do
a <- VU.unsafeRead v (i-2)
b <- VU.unsafeRead v (i-1)
VU.unsafeWrite v i (a + b)
return vЭтот подход использует O(n) памяти, но она предсказуема и вы освобождаете вектор по завершении.4) Если вы хотите сохранить ленивый infinite list, но избежать удержания старых элементов, не храните его в top-level CAF. Генерируйте список локально в месте использования и потребляйте его «стримингообразно» без сохранения ссылки на голову; тогда GC сможет освобождать пройденное. Но это ненадёжно и зависит от того, как именно используется список.Резюме / рекомендацииОпределение fibs = 0:1:zipWith (+) fibs (tail fibs) — удобно, лениво и с шеринго́м; хорошо, если вы хотите кешировать префикс и многократно читать одни и те же элементы.Если нужно контролируемое, предсказуемое использование памяти при доступе к n-му элементу, лучше использовать строгую хвостовую рекурсию или строгие свёртки (foldl') — это даёт O(n) время и O(1) доп. памяти по длине префикса.Следите за типами (Integer vs Int) и за тем, чтобы не накапливались thunk'и — используйте seq или BangPatterns или Data.Strict.Tuple, scanl' и т.п., когда нужно избежать отложенных вычислений.Если хотите, могу привести конкретные варианты кода (с BangPatterns, с scanl', с Vector) и измерения потребления памяти для разных n.
Еще 124
1
Что часто ищут
Поможем написать учебную работу