Unknown - haskell-notes

Здесь есть возможность читать онлайн «Unknown - haskell-notes» весь текст электронной книги совершенно бесплатно (целиком полную версию без сокращений). В некоторых случаях можно слушать аудио, скачать через торрент в формате fb2 и присутствует краткое содержание. Жанр: Старинная литература, на английском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале библиотеки ЛибКат.

haskell-notes: краткое содержание, описание и аннотация

Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «haskell-notes»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.

haskell-notes — читать онлайн бесплатно полную книгу (весь текст) целиком

Ниже представлен текст книги, разбитый по страницам. Система сохранения места последней прочитанной страницы, позволяет с удобством читать онлайн бесплатно книгу «haskell-notes», без необходимости каждый раз заново искать на чём Вы остановились. Поставьте закладку, и сможете в любой момент перейти на страницу, на которой закончили чтение.

Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

->

c c d b b e

6 4 5 5 3 1

f g d b e e

2 2 4 5 3 7

f g g h h e

Для представления двумерного массива мы воспользуемся типом Arrayиз стандартного модуля

Data.Array. Тип Arrayимеет два параметра:

data Arrayi a

Первый указывает на индекс, а второй на содержание. Массивы уже встречались нам в главе о типе ST.

Напомню, что подразумевается, что этот тип является экземпляром класса Ix, который описывает целочис-

ленные индексы, вспомним его определение:

class Orda => Ixa where

range

::(a, a) ->[a]

index

::(a, a) ->a -> Int

inRange

::(a, a) ->a -> Bool

rangeSize

::(a, a) -> Int

Первый аргумент у всех этих функций это пара, которая представляет верхнюю и нижнюю грань после-

довательности. Попробуйте догадаться, что делают методы этого класса по типам и именам.

Для двумерного массива индекс будет задаваться парой целых чисел:

import Data.Array

type Coord =( Int, Int)

type HeightMap = Array Coord Int

type SinkMap

= Array Coord Coord

Значение типа HeightMapхранит карту высот, значение типа SinkMapхранит в каждой координате, ту

точку, которая является водостоком для данной точки. Нам необходимо построить функцию:

flow :: HeightMap -> SinkMap

Мы будем решать эту задачу рекурсивно. Представим, что мы знаем водостоки для всех точек кроме

данной. Для каждой точки мы можем узнать в какую сторону из неё стекает вода. При этом водосток для

следующей точки такой же как и для текущей. Если же из данной точки вода никуда не течёт, то она сама

является водостоком. Мы определим эту функцию через комбинатор неподвижной точки fix.:

flow :: HeightMap -> SinkMap

flow arr =fix $\result ->listArray (bounds arr) $

map (\x ->maybe x (result !) $getSink arr x) $

range $bounds arr

getSink :: HeightMap -> Coord -> Maybe Coord

Мы ищем решение в виде неподвижной точки функции, которая принимает карту стоков и возвращает

карту стоков. Функция getSink по данной точке на карте вычисляет соседнюю точку, в которую стекает вода.

Эта функция частично определена, поскольку для водостоков нет такой соседней точки, в которую бы утекала

вода. Функция listArray конструирует значение типа Arrayиз списка значений. Первым аргументом она

принимает диапазон значений для индексов. Размеры массива совпадают с размерами карты высот, поэтому

первым аргументом мы передаём bounds arr.

Теперь разберёмся с тем как заполняются значения в список. Сначала мы создаём список координат

исходной карты высот с помощью выражения:

range $bounds arr

После этого мы по координатам точек находим водостоки, причём сразу для всех точек. Это происходит

в лямбда-функции:

\x ->maybe x (result !) $getSink arr x

Водосборы | 187

Мы принимаем текущую координату и с помощью функции getSink находим соседнюю точку, в которую

убегает вода. Если такой точки нет, то в следующем выражении мы вернём исходную точку, поскольку в этом

случае она и будет водостоком, а если такая соседняя точка всё-таки есть мы спросим результат из будущего.

Мы обратимся к результату (result !), посмотрим каким окажется водосток для соседней точки и вернём

это значение. Поскольку за счёт ленивых вычислений значения результирующего массива вычисляются лишь

один раз, после того как мы найдём водосток для данной точки этим результатом смогут воспользоваться

все соседние точки. При этом порядок обращения к значениям из будущих вычислений не играет роли.

Осталось только определить функцию поиска ближайшего стока и функцию разметки.

getSink :: HeightMap -> Coord -> Maybe Coord

getSink arr (x, y)

|null sinks = Nothing

|otherwise

= Just $snd $minimum $map (\i ->(arr !i, i)) sinks

wheresinks =filter p [(x +1, y), (x -1, y), (x, y -1), (x, y +1)]

p i

=inRange (bounds arr) i &&arr !i <arr !(x, y)

В функции разметки мы воспользуемся ассоциативным массивом из модуля Data.Map. Функция nub из

модуля Data.Listубирает из списка повторяющиеся элементы. Затем мы составляем список пар из коорди-

нат водостоков и меток и в самом конце размечаем исходный массив:

label :: SinkMap -> LabelMap

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Похожие книги на «haskell-notes»

Представляем Вашему вниманию похожие книги на «haskell-notes» списком для выбора. Мы отобрали схожую по названию и смыслу литературу в надежде предоставить читателям больше вариантов отыскать новые, интересные, ещё непрочитанные произведения.


Отзывы о книге «haskell-notes»

Обсуждение, отзывы о книге «haskell-notes» и просто собственные мнения читателей. Оставьте ваши комментарии, напишите, что Вы думаете о произведении, его смысле или главных героях. Укажите что конкретно понравилось, а что нет, и почему Вы так считаете.

x