LINUX.ORG.RU

[Haskell] Нормальная ли структура программы?


0

1

Здравствуйте. Изучаю хаскель (по LYAH). В качестве упражнения решил написать небольшую программу для геометрических вычислений: http://paste.org.ru/?qq9jwi

Есть 2 вопроса:
1) Нормальна ли такая структура программы? Лично мне не нравятся конструкторы. Напр. основной Vector x y, и дополнительные vectorFromPoint, vectorFromPoints...: длинные имена, да и основной конструктор с большой буквы, а остальные с маленькой — не красиво. Можно ли как-нибудь сделать функцию, скажем, fromPoints, которая вернет либо вектор, либо отрезок, либу прямую... в зависимости от требуемого типа (напр. vectorLength (fromPoints p q) — тут же хаскель сам может догадаться, что нужен вектор).

2) Вообще, этот код не работает. Выдает это:

/home/toady/xlam/geometr/geom.hs:66:6:
    Couldn't match expected type `f' against inferred type `Circle'
      `f' is a rigid type variable bound by
          the type signature for `area'
            at /home/toady/xlam/geometr/geom.hs:65:16
    In the pattern: Circle _ r
    In the definition of `area': area (Circle _ r) = pi * r ^ 2

/home/toady/xlam/geometr/geom.hs:69:11:
    Couldn't match expected type `f' against inferred type `Circle'
      `f' is a rigid type variable bound by
          the type signature for `perimeter'
            at /home/toady/xlam/geometr/geom.hs:68:21
    In the pattern: Circle _ r
    In the definition of `perimeter':
        perimeter (Circle _ r) = 2 * pi * r

/home/toady/xlam/geometr/geom.hs:72:46:
    Couldn't match expected type `Point' against inferred type `f'
      `f' is a rigid type variable bound by
          the type signature for `distance'
            at /home/toady/xlam/geometr/geom.hs:71:20
    In the first argument of `vectorFromPoints', namely `p'
    In the first argument of `vectorLength', namely
        `(vectorFromPoints p q)'
    In the expression: vectorLength (vectorFromPoints p q)
Failed, modules loaded: none.
Как можно починить?


class FromPoints f where
  fromPoints :: Point -> f

?

anonymous ()

Сделал так: http://paste.org.ru/?3de4bo

Но есть одна проблема: я хочу определить dist (расстояние), но чтобы она работало с dist (Point ...) (Circle ...) и т.д., т.е. чтобы можно было разные фигуры указывать.

Я сделал dist частью класса Figure. Когда я определяю в instance Figure Point функцию dist (Point ...) (Line ...), то выдается ошибка, т.к. Line я включаю в Figure ниже (наверно в этом причина). Но если я поставлю instance Line перед instance Point, то произоёдет та же самая ошибка, когда я буду определять dist (Line ...) (Point ...) в instance Line. Как быть?

toady2 ()
Ответ на: комментарий от toady2

P.S. Если dist убрать из class Figure. И далее определять её как

dist :: (Figure f, Figure g) => f -> g -> Float
dist (Point x y) (Line p q) = ...
...
то тоже выдается ошибка.

toady2 ()

В качестве упражнения решил написать небольшую программу для геометрических вычислений

А у меня было так

quasimoto ★★★★ ()

> конструкторы ... дополнительные vectorFromPoint, vectorFromPoints ... с маленькой

это не конструкторы

korvin_ ★★★★★ ()
Ответ на: комментарий от toady2

> По-моему, это ещё хуже.

почему? это нормально.

korvin_ ★★★★★ ()
Ответ на: комментарий от toady2

вопрос:

Можно ли как-нибудь сделать функцию, скажем, fromPoints, которая вернет либо вектор, либо отрезок, либу прямую... в зависимости от требуемого типа

По-моему, это ещё хуже.

По-моему, лучше.

anonymous ()
Ответ на: комментарий от anonymous

Ок. Ну это ладно. Меня теперь особенно интересует, как задать функцию dist, которая может принимать значения разных типов (входящих в класс Figure).

toady2 ()
Ответ на: комментарий от toady2

> Если dist убрать из class Figure. И далее определять её как

для g известно лишь то, что оно экземпляр Figure.

anonymous ()
Ответ на: комментарий от anonymous

Да. Line ведь входит в Figure. И Point тоже.

А можно просто определить как-то так (это не работает, но идею, надеюсь, вы поняли):

dist :: Circle -> Point -> Float
dist = ...

dist :: Line -> Point -> Float
dist = ...
...

Как вообще осуществлять «перегрузку» функции по аргументам в Хаскеле?

toady2 ()
Ответ на: комментарий от toady2
-- 1) Не надо писать аккессоры (pointX/Y и прочие) - паттерн-матчинг ведь,
--    ну и structure-syntax если нужна подробная спецификация
-- 2) Не нужну дублировать Point и Vector - это одно и то же (вектора должны
--    быть свободными)
-- 3) Про Segment и Line - тоже самое
-- 4) Какой смысл в тайпклассах? (что означает длина и площадь? жордановые меры
--    - ещё куда ни шло :))
-- 5) Прочая машинерия тоже не нужна

-- |
-- Just the data types
--
data Point  = Point  Float Float deriving (Eq, Show)
data Line   = Line   Point Point deriving (Eq, Show)
data Circle = Circle Point Float deriving (Eq, Show)

-- |
-- When we want to meet Jordan-measures (in 2D)
--
class Figure f where
  measure'1 :: f -> Float
  measure'2 :: f -> Float -- oops!

instance Figure Point where
  measure'1 _ = 0
  measure'2 _ = 0

instance Figure Line where
  measure'1 (Line (Point x1 y1) (Point x2 y2))
   = sqrt ((x2 - x1)^2 + (y2 - y1)^2)
  measure'2 _ = 0

instance Figure Circle where
  measure'1 (Circle _ r) = 2 * pi * r
  measure'2 (Circle _ r) = pi * r^2

-- |
-- Some functions
--
makeLine :: Point -> Point -> Line
makeLine (Point x1 y1)  (Point x2 y2) = (Line (Point x1 y1) (Point x2 y2))
quasimoto ★★★★ ()
Ответ на: комментарий от toady2

Как вообще осуществлять «перегрузку» функции по аргументам в Хаскеле?

Внутри instance - например, выше measure'1 и measure'2 имеют разные спецификации для разных типов (Point, Line, Circle) одного класса типов (Figure).

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

Спасибо!

-- 1) Не надо писать аккессоры (pointX/Y и прочие) - паттерн-матчинг ведь, -- ну и structure-syntax если нужна подробная спецификация

-- 2) Не нужну дублировать Point и Vector - это одно и то же (вектора должны -- быть свободными)

-- 3) Про Segment и Line - тоже самое

-- 4) Какой смысл в тайпклассах? (что означает длина и площадь? жордановые меры -- - ещё куда ни шло :))

-- 5) Прочая машинерия тоже не нужна

1) А если нет возможности паттерн-матчинга, напр

foo = pointX (intersect (Line p q) (Line r s))


2) Это только для удобства чтения. Может type Point = Vector лучше?
3) Не согласен. В случае реализации функции пересечения будет разница.
4) У вас же тоже используется тайпклассы (Figure)?

Еще не понял, зачем нужна makeLine, если можно явно писать Line ...?

toady2 ()
Ответ на: комментарий от toady2

> Как вообще осуществлять «перегрузку» функции по аргументам в Хаскеле? [code] class Bi t t0 where distance :: (Figure t, Figure t0) => t -> t0 -> Float [/code]

anonymous ()
Ответ на: комментарий от anonymous

Как вообще осуществлять «перегрузку» функции по аргументам в Хаскеле? [code]

class Bi t t0 where distance :: (Figure t, Figure t0) => t -> t0 -> Float

anonymous ()
Ответ на: комментарий от quasimoto

Внутри instance - например, выше measure'1 и measure'2 имеют разные спецификации для разных типов (Point, Line, Circle) одного класса типов (Figure).

Не очень понял. Я выше писал проблему: я определяю dist (Line ...) (Point ...), а instanse Figure Point делается ниже. Если же поднять instanse Figure Point наверх, то instanse Figure Line окажется ниже и получится та же проблема.

toady2 ()
Ответ на: комментарий от anonymous

Что такое Bi? То есть

class Bi t t0 where 
    distance :: (Figure t, Figure t0) => t -> t0 -> Float 
    distance (Line...) (Point...) =...
    distance (Circle...) (Line...) =...
Так? Почему без Bi нельзя?

toady2 ()
Ответ на: комментарий от toady2

> Так? Почему без Bi нельзя?

а ты не видишь, что Bi параметризуется двумя типами — t и t0?

korvin_ ★★★★★ ()

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

toady2 ()
Ответ на: комментарий от korvin_

Ясно. Но неужели это единственный способ «перегрузки»? Просто выглядит, пардон, как костыль — вводится новый тайпкласс только для того, чтобы сделать перегрузку.

toady2 ()
Ответ на: комментарий от toady2

> Ясно. Но неужели это единственный способ «перегрузки»? Просто выглядит, пардон, как костыль — вводится новый тайпкласс только для того, чтобы сделать перегрузку.

это не «костыль», а строгая типизация

korvin_ ★★★★★ ()
Ответ на: комментарий от toady2

1) Структурный синтаксис:

data Point' = Point' { pointX :: Float,
                       pointY :: Float }
            deriving (Eq, Show)

(Point' 1 2)
> Point' {pointX = 1.0, pointY = 2.0}

Point' {pointX = 1.0, pointY = 2.0}
> Point' {pointX = 1.0, pointY = 2.0}

pointX (Point' 1 2)
> 1.0

на этом же основана техника опциональных аргументов (http://neilmitchell.blogspot.com/2008/04/optional-parameters-in-haskell.html)

2) Да, type Point = Vector - как синоним типа. Но это увеличивает информацию о коде (помнить что это одно и то же).

3) Аналогично - типы не отличимы, поэтому type Segment = Line, но опять таки это лишние сущности. Если нужны разные функции для Line (в смысле Line и в смысле Segment), то это должны быть разные функции для одного типа Line - это не ООП, т.е. мы не будем делать одинаковые классы с разными методами (т.к. ни того ни другого нет - есть тип и функции).

4) Ну да, как пример на эту тему. Вот ещё пример - https://github.com/sebfisch/haskell-regexp/blob/master/src/Data/Semiring.hs, определяется класс типов semiring, при этом для конкретных полуколец определяются свои единицы, нули и бинарные опперации. Получается, что функции могут работать для разных типов. А вот в https://github.com/sebfisch/haskell-regexp/blob/master/src/Data/Semiring/Properties.hs определяются функции уже над любыми полукольцами (generic programming) (в единственном числе - было бы странно иметь функции в математическом смысле с разными определениями).

5) Ну это просто так - мы можем писать конкретную функцию a -> b, либо функцию в контексте (Foo t) => t -> a. Это был пример без контекста. По последней ссылке выше - пример с контекстом.

quasimoto ★★★★ ()
Ответ на: комментарий от toady2

Я выше писал проблему: я определяю dist (Line ...) (Point ...), а instanse Figure Point делается ниже.

Просто жордановая мера фигуры это один кусок (действительно - класс всех возможных типов фигур). А «расстояние» между фигурами (некая метрика) это совсем другой кусок:

{-# LANGUAGE MultiParamTypeClasses #-}

-- ^ at the begining

-- ...

-- v at the end

-- |
-- When man stumbling with warm fuzzy things
--
class TryToRoadFromTo f g where
  road :: f -> g -> Float

instance TryToRoadFromTo Point Line where
  road (Point a b) (Line (Point x1 y1) (Point x2 y2)) = ...
quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

А TryToRoadFromTo это как-то в геодезии называется :) Установление пути между площадями.

quasimoto ★★★★ ()
Ответ на: комментарий от toady2

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

Ну а чтобы по трём аргументам - ещё один тайпкласс :) И так далее (см. Type Classes with Functional Dependencies). Даже специальную директиву для разрешения такого поведения нужно ставить.

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

забыл фичу

- class TryToRoadFromTo f g where
+ class (Figure f, Figure g) => TryToRoadFromTo f g where
quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

А можно ли сделать, чтобы * и + над работали над векторами (давали скал. произведение и сумму). Или так перегрузить нельзя и надо новое обозначение вводить?

toady2 ()
Ответ на: комментарий от toady2

Можно (http://www.haskell.org/onlinereport/modules.html)

module Geom ( (+), (-), (*), (/) ) where
import qualified Prelude
import Prelude hiding ((+), (-), (*), (/))

infixr 6 +
infixr 6 -
infixr 7 *
infixr 7 /

data Vector f = Vector f f deriving (Eq, Show)

(+) :: (Num f) => (Vector f) -> (Vector f) -> (Vector f)
(Vector x1 y1) + (Vector x2 y2) = Vector (x1 Prelude.+ x2) (y1 Prelude.+ y2)

(-) :: (Num f) => (Vector f) -> (Vector f) -> (Vector f)
(Vector x1 y1) - (Vector x2 y2) = Vector (x1 Prelude.- x2) (y1 Prelude.- y2)

(*) :: (Num f) => f -> (Vector f) -> (Vector f)
s * (Vector x y) = Vector (s Prelude.* x) (s Prelude.* y)

(/) :: (Fractional f, Num f) => (Vector f) -> f -> (Vector f)
(Vector x y) / s = Vector (x Prelude./ s) (y Prelude./ s)

-- > (Vector 2 2) + (Vector 4 4) - (Vector 2 2) / 2
-- > >> Vector 5.0 5.0

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

infixr 6 ⊕
infixr 6 ⊖
infixr 7 ⊙
infixr 7 ⊘

data Vector f = Vector f f deriving (Eq, Show)

(⊕) :: (Num f) => (Vector f) -> (Vector f) -> (Vector f)
(Vector x1 y1) ⊕ (Vector x2 y2) = Vector (x1 Prelude.+ x2) (y1 Prelude.+ y2)

(⊖) :: (Num f) => (Vector f) -> (Vector f) -> (Vector f)
(Vector x1 y1) ⊖ (Vector x2 y2) = Vector (x1 Prelude.- x2) (y1 Prelude.- y2)

(⊙) :: (Num f) => f -> (Vector f) -> (Vector f)
s ⊙ (Vector x y) = Vector (s Prelude.* x) (s Prelude.* y)

(⊘) :: (Fractional f, Num f) => (Vector f) -> f -> (Vector f)
(Vector x y) ⊘ s = Vector (x Prelude./ s) (y Prelude./ s)

-- > (Vector 2 2) ⊕ (Vector 4 4) ⊖ (Vector 2 2) ⊘ 2
-- > >> Vector 5.0 5.0

можно без юникода - .+. какой-нибудь

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

т.е. профит в

(Vector 2 2) ⊕ (Vector (4 + 5) (4 - 1)) ⊖ (Vector 2 2) ⊘ (2 * 2)
>> Vector 10.5 4.5

кстати, вот разрулить приоритеты векторных и скалярных тут - может быть удобно.

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

Посмотрите, пожалуйста — http://paste.org.ru/?pko74p. Меня волнует больше сама структура кода, она нормальная?

Сделать type Vector = Point не получилось. Выдаётся ошибка, что Vector не конструктор.

toady2 ()
Ответ на: комментарий от toady2

Сделать type Vector = Point не получилось. Выдаётся ошибка, что Vector не конструктор.

Естественно, ведь конструктора данных Vector больше не существует, остался только конструктор типа Vector. Там где выдаёт ошибку, нужно поменять Vector на Point. Попробуй называть их по-разному, например,

data VectorT = VectorD Float Float
чтобы понять, где тип, а где данные.

exlevan ()

Ещё я хочу сделать вместо

...
class (Figure f, Figure g) => HaveIntersection f g where
    cap :: f -> g -> [Point] -- пересечение
...
как-то так
...
instance Figure [Point]
...
class (Figure f, Figure g) => HaveIntersection f g where
    cap :: (Figure h) => f -> g -> [h]
...
Напр. при пересечении двух треугольников результатом может быть другой треугольник, при пересечении треугольника и прямоугольника — отрезок и т. д. Т. е. результатом может быть любое множество фигур (входящих в класс Figure). Но ghc ругается как на instance Figure [Point] (instance Figure Point работает), так и на новое определение cap.

toady2 ()
Ответ на: комментарий от toady2

ghc ругается как на instance Figure [Point]

Как ругается? FlexibleInstances просит?

cap :: (Figure h) => f -> g -> [h]

Плохой тип, неправильный. Читается как «любая фигура h может являться пересечением фигур f и g». А нужно «существует фигура h, являющаяся пересечением фигур f и g». Это в сторону экзистенциальных типов (расширение ExistentialQuantification).

А можно просто ввести ассоциированный тип для класса Figure (расширение TypeFamilies). Выглядеть будет примерно так:

--

class (Figure f, Figure g) => HaveIntersection f g where
    type Intersection
    cap :: f -> g -> Intersection

instance HaveIntersection Line Line where
    type Intersection = Either Point Line
    cap l1@(Line k1 b1) l2@(Line k2 b2) = if l1 == l2
        then Right l1
        else Left $ Point x y
      where
        x = (b2-b1)/(k1-k2)
        y = k1*x+b1

instance HaveDistance Point Line where
    dist p z@(Line a b) = case cap z $ l'perp z p of
        Left p' -> len $ Segment p p'
        Right _ -> 0

exlevan ()
Ответ на: комментарий от exlevan

Выглядеть будет примерно так:

Это не совсем то. Напр. при пересечении двух равных линий cap должен возвратить [Line]. Если прямые параллельны — то []. То есть типа такого

instance HaveIntersection Line Line where
    cap l1@(Line k1 b1) l2@(Line k2 b2) =
        | l1 == l2 = [l1]
        | k1 == k2 = []
        | otherwise = [Point x y] where
            x = (b2-b1)/(k1-k2)
            y = k1*x+b1
Но при пересечении других фигур может быть результаты другие, но в общем случае список фигур (в класс Figure входят Point, Segment...)

Это в сторону экзистенциальных типов

Я почитал в интернете про ExistentialQuantification, но что-то совсем ничего не понял :((

toady2 ()
Ответ на: комментарий от toady2

Это не совсем то.

Почему не совсем то? У меня примерно так и сделано, возвращается точка пересечения или линия, если линии равны. Вариант с параллельными не учёл, каюсь. Но в остальном не вижу ничего плохого. А если делать список фигур (любых), через экзистенциальные типы, то к нему можно применять функции, работающие на произвольных фигурах. То есть определённые в классе Figure. Но так как в классе этом функций сейчас нет, то максимум, что с этим списком получится потом сделать — посчитать, из скольки фигур состоит пересечение. Не густо, в общем.

Для ясности, ещё один экземпляр, для двух точек:

instance HasIntersection Point Point where
    type Intersection = Maybe Point -- пересечение равно Just point, если точки совпадают,
                                    -- или Nothing в противном случае
    cap p1 p2 = if p1 == p2 then Just p1 else Nothing

Я почитал в интернете про ExistentialQuantification, но что-то совсем ничего не понял :((

Попробую показать на примере.

{-# LANGUAGE ExistentialQuantification #-}
module Main where

-- какой-то класс
class Klass a where
    klassFun :: a -> Integer

-- экземпляр класса Klass
data Ins1 = Ins1 Integer

instance Klass Ins1 where
    klassFun (Ins1 x) = x

ins1fun :: Ins1 -> Integer
ins1fun (Ins1 x) = x + 5

-- ещё один экземпляр
data Ins2 = Ins2 Integer

instance Klass Ins2 where
    klassFun (Ins2 x) = -x

ins2fun :: Ins2 -> Integer
ins2fun (Ins2 x) = x * 2

-- экзистенциальная типизация
-- Тип 'a' присутствует в данных, но не в типе
data Klass' = forall a. Klass a => Klass' a

-- теперь Ins1 и Ins2 можно поместить в один список
inss :: [Klass']
inss = [Klass' $ Ins1 5, Klass' $ Ins2 10]

-- но после запечатывания в Klass' обратно Ins1 и Ins2 уже не получить
-- можно применять только общие для Klass функции, например:
-- map (\(Klass' x) -> klassFun x) inss
-- > [5,-10]
-- но ins1fun и ins2fun уже не применить, они недостаточно общие
exlevan ()
Ответ на: комментарий от exlevan

Ладно. Я сам запутался в том, что хочу. Давайте я лучше напишу то, что я хочу *получить*. Я хочу сделать простенькую решалку геометрических задач.

Предположим: Имеется равнобокая трапеция ABCD (AD||BC, AD>BC). В неё вписана окружность. Прямая AO пересекает сторону CD в точке K. Отрезки AO=5, OK=4.

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

geom> t = Polygon A B C D
Undefined: B, C, D   -- точка A фиксируется где-угодно

geom> Circle O r = inCircle t
Undefined: B, C, D, O, r

geom> parallel (Line A D) (Line B C)
Undefined: B, C, D, O, r

geom> len (Segment A D) == len (Segment B C)
Undefined: B, C, D, O, r

geom> K = (Line A O) `cap` (Segment C D)
Undefined: B, C, D, O, r, K

geom> len (Segment A O) == 5
Undefined: B, C, D, r, K

geom> len (Segment O K) == 4
All defined

geom> print B R (area (Circle O R))
B = ...
R = ...
area (Circle O R) = ...

Надеюсь идею вы поняли: мы вводим новые элементы и ограничения на них до тех пор, пока все элементы не станут определены. Ну так вот: на чём это можно реализовать (в смысле проще всего)? И если можно на хаскеле, то примерно как?

toady2 ()
Ответ на: комментарий от toady2

Посмотрите, пожалуйста — http://paste.org.ru/?pko74p. Меня волнует больше сама структура кода, она нормальная?

Мне не очень нравится :) Попробую объяснить почему.

Всегда нужно начинать с того чтобы очертить предметную область. В данном случае мы хотим как-то оперировать геометрическими фигурами, поэтому предметной область являются фигуры на плоскости. Все фигуры разные (структурно разные), поэтому, как обычно, специфицировать объекты предметной области можно с помощью АТД (алгебраических/абстрактных типов данных). С помощью data мы задаём конкретные АТД для фигур, при этом получается иерархия (вектор это tuple над полем, точка выражается через вектор, линия через две точки, окружность через точку и элемент поля, полигональная фигура через набор точек или линий с условие замкнутости). data задаёт во-первых тип(ы), во-вторых конструкторы, поэтому как только мы определили наши предметные объекты (фигуры) с помощью data (спецификация АТД), мы уже можем их конструировать и писать специфичные функции (специфика это всегда определённые типы аргументов у таких функций, никаких «перегрузок»). А вот type определяет только синоним типа - не конструкторы! Тем не менее можно делать instance класса (class) не только от типов (data), но и от их синонимов (type) - TypeSynonymInstances.

Следующее что нужно сделать - выделить наиболее общую категорию (не ту) для всевозможных фигур. Обычно таким обобщением является определение класса типов. И в данном случае это класс типов Figure. Что это такое? Это не «класс» (не тот!), это не нечто что «наследуется». Это просто «что-то» позволяющее ввести набор функций которые будут «работать» для всех типов-инстансов (это не «наследование») этого «чего-то» (и это не «класс» в привычном смысле, ещё раз). Да, похоже на «перегрузку», но лучше так не думать - это скорее параметрический полиморфизм позволяющий писать обобщённые функции. Кстати, это возможная проверка - вот вы ввели класс типов и можно сразу пробовать писать обобщённые функции - если пишутся легко, значит ввели правильный класс, а если не очень - значит что-то не так надумали. В данном случае тип классов должен быть один - Figure, и включать в себя функции для получения жордановых мер фигуры (длина, площадь), для нахождения центра фигуры, и прочее - нечто общее для всех фигур. Тогда дистанция, пересечение и прочие функции будут просто обобщёнными функциями (не новыми классами, этих классов в мире вообще мало (т.е. в принципе) - нужно подумать прежде чем определить новый).

Это примерная схема использования ключевых слов (data, type, class, instance, про newtype не сказал). Заметьте цепочку:

1) Определили предметную область, специфицировали её объекты с помощью АТД (data, type, newtype),

2) Написали специфичные (неполиморфные) функции для этих АТД.

3) Объекты предметной области составляют некоторую «структуру» (в смысле «алгебраическая структура»), которую мы выделили как некую общность этих объектов с помощью класса типов (это может быть моноид, полукольцо, категория, любая другая алгебраическая структура, см. typeclassopedia).

4) Написали обобщённые (параметрически полиморфные) функции для элементов этой «структуры».

quasimoto ★★★★ ()
Ответ на: комментарий от toady2

Вот пример того как это может выглядеть:

{-# LANGUAGE TypeSynonymInstances #-}

-- |
-- Модуль : Geom
-- 
--   Простая евклидовая геометрия.
-- 
module Geom (

  Vector(..), zero'vector,

  (.+.), (.-.), (.*.), (./.), (.**.),

  Point(..), point, distance'point,

  Line(..),

  Circle(..),

  Polygonal, polygonal'lines, rectangle,

  Figure(..),

  distance, sum'area, sum'len,

  (↑), (↓), (×),

  quadrilateral'include'point, line'intersect'quadrilateral

 ) where

-- |
-- Вектор как элемент 2-мерного линейного векторного пространства V над числовым полем F.
--
data Vector f = Vector { vector'x :: f, vector'y :: f } deriving (Eq, Show)

-- | Нулевой вектор.
zero'vector = Vector 0 0

-- |
-- Основные бинарные операции над V и F.
-- |

infixr 6 .+.
infixr 6 .-.
infixl 7 .*.
infixr 7 ./.
infixr 8 .**.

-- | Сумма векторов.
(.+.) :: (Num f) => (Vector f) -> (Vector f) -> (Vector f)
(Vector x1 y1) .+. (Vector x2 y2) = Vector (x1 + x2) (y1 + y2)

-- | Разность векторов.
(.-.) :: (Num f) => (Vector f) -> (Vector f) -> (Vector f)
(Vector x1 y1) .-. (Vector x2 y2) = Vector (x1 - x2) (y1 - y2)

-- | Умножение вектора на скаляр.
(.*.) :: (Num f) => f -> (Vector f) -> (Vector f)
s .*. (Vector x y) = Vector (s * x) (s * y)

-- | Деление вектора на скаляр.
(./.) :: (Fractional f, Num f) => (Vector f) -> f -> (Vector f)
(Vector x y) ./. s = Vector (x / s) (y / s)

-- | Cкалярное проезведение векторов (евклидово пространство).
(.**.) :: (Num f) => (Vector f) -> (Vector f) -> f
(Vector x1 y1) .**. (Vector x2 y2) = x1 * x2 + y1 * y2

-- |
-- АТД описывающие предметную область (геометрические фигуры).
--
--   В качестве поля используется Float.
--
-- |

-- |
-- Точка как вектор.
--
data Point = Point { point'vector :: (Vector Float) } deriving (Eq, Show)

-- | Упрощённая функция-конструктор для точки.
point :: Float -> Float -> Point
point x y = Point (Vector x y)

-- | Расстояние между точками.
distance'point :: Point -> Point -> Float
distance'point (Point (Vector x1 y1)) (Point (Vector x2 y2))
  = sqrt ((x2 - x1)^2 + (y2 - y1)^2)

-- |
-- Линия как две точки.
--
data Line = Line { line'from :: Point, line'to :: Point } deriving (Eq, Show)

-- |
-- Окружность как точка и радиус.
--
data Circle = Circle { circle'center :: Point, circle'radius :: Float } deriving (Eq, Show)

-- |
-- Полигональная фигура как множество точек.
--
type Polygonal = [Point]

-- | Линии полигональной фигуры.
polygonal'lines :: Polygonal -> [Line]
polygonal'lines figure = collect'lines figure
                       where
                         collect'lines (x:[]) = (Line x (head figure)) : []
                         collect'lines (x:xs) = (Line x (head xs)) : (collect'lines xs)

-- | Функция-конструктор для примоугольника.
rectangle :: Point -> Float -> Float -> Polygonal
rectangle (Point (Vector x y)) dx dy = [(point x        y)
                                       ,(point (x + dx) y)
                                       ,(point (x + dx) (y + dy))
                                       ,(point x        (y + dy))]

-- |
-- Классы типов нужны для того чтобы писать обощённые функции для объектов предметной области
-- (представленных с помощью АТД). "классы" тут ни при чём, также как и "наследование".
-- |

-- |
-- Фигура как класс типов для всех объектов имеющих жордановые меры (и другие харрактеристики).
--
class Figure f where
  center :: f -> Point -- центр фигуры
  len    :: f -> Float -- жорданова мера 1
  area   :: f -> Float -- жорданова мера 2

-- |
-- Точка как фигура.
--
instance Figure Point where
  center f = f
  len    _ = 0
  area   _ = 0

-- |
-- Линия как фигура.
--
instance Figure Line where
  center (Line (Point (Vector x1 y1)) (Point (Vector x2 y2)))
                 = point ((x2 - x1) / 2) ((y2 - y1) / 2)
  len (Line a b) = distance'point a b
  area _         = 0

-- |
-- Окружность как фигура.
--
instance Figure Circle where
  center (Circle p _) = p
  len    (Circle _ r) = 2 * pi * r
  area   (Circle _ r) = pi * r^2

-- |
-- Случай полигональной фигуры.
--
instance Figure Polygonal where
  center f = undefined -- неохота
  len    f = sum (map len (polygonal'lines f))
  area   f = undefined -- и это тоже

-- |
-- Примеры обощённых функций.
-- |

-- | Расстояния между фигурами.
distance :: (Figure f, Figure g) => f -> g -> Float
distance f g = distance'point (center f) (center g)

-- | Общая площадь двух фигур (без пересечений).
sum'area :: (Figure f, Figure g) => f -> g -> Float
sum'area f g = (area f) + (area g)

-- | Общая длинна двух линий (без совпадений).
sum'len :: (Figure f, Figure g) => f -> g -> Float
sum'len f g = (len f) + (len g)

-- KLUDGE: нужны гетерогенные списки:
--   sum'area :: (Figure f ? ) => List f -> Float
--   sum'area fs = sum (map area fs)

-- |
-- Логическая часть.
--
--   Под "логикой" подрузумевается возможность ввести базовые геометрические предикаты так,
--   что любая логическая (на тему "да" или "нет") задача евклидовой геометрии может быть
--   решена в терминах языка этих предикатов.
--
--   Утверждается, что достаточный язык следующий:
--
--     EPrim ::= Point ↑ Line
--     Log1  ::= not
--     Log2  ::= or | and
--     EExpr ::= EPrim | Log1 EExpr | Log2 EExpr EExpr
--
--   Где ↑ это основной геометрический предикат, по отношению к которому все остальные предикаты
--   являются производными.
--
-- |

infixr 6 ×
infixr 7 ↑
infixl 7 ↓

-- | Базовый геометрический предикат - в какой полуплоскости относительно линии лежит точка?
(↑) :: Point -> Line -> Bool
(Point (Vector x y)) ↑ (Line (Point (Vector x1 y1)) (Point (Vector x2 y2)))
  = if x1 == x2
    then x < x1
    else if y1 == y2
         then y > y1
         else (y / x) > ((y2 - y1) / (x2 - x1))

(↓) :: Point -> Line -> Bool
point ↓ line = not (point ↑ line)

-- | Пересекаются ли линии?
(×) :: Line -> Line -> Bool
line1@(Line p11 p12) × line2@(Line p21 p22)
  =    (((p11 ↑ line2) && (p12 ↓ line2)) || ((p11 ↓ line2) && (p12 ↑ line2)))
    && (((p21 ↑ line1) && (p22 ↓ line1)) || ((p21 ↓ line1) && (p22 ↑ line1)))

-- | Точка внутри 4-угольника?
quadrilateral'include'point :: Polygonal -> Point -> Bool
quadrilateral'include'point figure point = let lines = (polygonal'lines figure)
                                           in    (point ↑ (lines !! 0))
                                              && (point ↑ (lines !! 1))
                                              && (point ↓ (lines !! 2))
                                              && (point ↓ (lines !! 3))

-- | Линия и 4-угольник пересекаются?
line'intersect'quadrilateral :: Line -> Polygonal -> Bool
line'intersect'quadrilateral line@(Line p1 p2) figure = or [(quadrilateral'include'point figure p1)
                                                           ,(quadrilateral'include'point figure p2)
                                                           ,(or (map (× line) (polygonal'lines figure)))]
quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto
- distance'point (Point (Vector x1 y1)) (Point (Vector x2 y2))
-   = sqrt ((x2 - x1)^2 + (y2 - y1)^2)
+ distance'point a b = sqrt ((point'vector a) .**. (point'vector b))
quasimoto ★★★★ ()
Ответ на: комментарий от toady2

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

Используйте undefined. В Haskell любой тип T это сам Т + примесь «невозможная ситуация»:

T = (T, _|_)

Это хорошо потому что это просто, можно следить за ошибками (хотя, какие ошибки в чистых функциях?) и использовать undefined. Почему это плохо - можете посмотреть `total functional programming'.

*Geom> let c = Circle (point 1 2) undefined
*Geom> area c
*** Exception: Prelude.undefined

*Geom> let l = Line (point 1 2) (point 2 3)
*Geom> len l
2.828427

Или имеется в виду что-то более сложное? Приведите какую-нибудь конкретную задачку которую можно так решить (сверху вниз).

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto
*Geom> let c = Circle (point 1 2) undefined

А если потом появятся условия, из которых этот undefined можно будет вывести?

Приведите какую-нибудь конкретную задачку которую можно так решить (сверху вниз).

Я уже привел выше (про трапецию). Может быть лучше не на Хаскеле реализовывать, а на чём-то другом. Я даже не знаю, как назвать эту парадигму: вроде и не функциональная, и не императивная... Вот мы ввели какой-то объект (скажем, многоугольник ABCD). О нем пока ничего неизвестно; можно только зафиксировать одну точку и одну координату соседней точки:

Состояние: A=(0,0), B=(?1,0), C=(?2,?3), D=(?4,?5)
-- ?<n> я обозначил неизвестную величину номер n
Но затем я ввожу ограничения, и интерпретатор должен наложить эти ограничения на имеющееся состояние «чертежа»: например, я задаю AB||CD, а интерпретатор определяет
Состояние: A=(0,0), B=(?1,0), C=(?2,?3), D=(?4,?3)
-- То есть стало известно, что ординаты C и D равны (?3)
Далее я задаю AB=5 и AB=CD. Интерпретатор определяет
Состояние: A=(0,0), B=(5,0), C=(?2,?3), D=(5+?2,?3)
И так далее до тех пор, пока неизвестных величин не останется: тогда я могу спросить любой элемент, напр
geom> print (distance B C)
10
Более практический пример про трапецию см. выше.

Вообще, как называется эта «парадигма», основанная на «состояниях», которые после каждой команды обновляется в связи с новыми данными?

toady2 ()
Ответ на: комментарий от toady2

То есть смысл в чем: таким образом можно решить любую детерминированную задачу из учебников по планиметрии. Вписываем условия и спрашиваем то, что мы хотим узнать.

С недетерминированными задачами (когда входные условия допускают различные ситуации (даже бесконечное число), но, тем не менее, искомый в задаче элемент во всех ситуациях один и тот же) сложнее. Но пока не будем голову забивать. (Впрочем, если задачка из учебника и *точно известно*, что искомый элемент один и тот же при любых ситуациях, то можно случайно выбрать одну из этих ситуаций и решить соответствующую детерминированную задачу)

toady2 ()
Ответ на: комментарий от toady2

> Я даже не знаю, как назвать эту парадигму: вроде и не функциональная, и не императивная...

логическая? constraint programming?

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

это ты практически описал работу интерпертатора пролога.

paranonymous ()
Ответ на: комментарий от toady2

таким образом можно решить любую детерминированную задачу из учебников по планиметрии.

Вы имеете в виду разрешимость? Tarski's axioms? Если да, то это алгоритм и он может быть реализован на любом языке. Но вряд ли это можно сделать просто :) Сначала нужно превратить понятную запись (как у вас в примере) в wff, потом сам алгоритм может иметь чудовищную сложность.

Что касается пролога - то там возможны геометрические доказатели (prolog geometry prover), но всё-таки он не нацелен на выражение произвольных логических систем. Есть другие языки в которых это возможно, но, опять-таки, может оказаться весьма сложным.

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

Вы имеете ввиду алгоритм Тарского? Я *не* собираюсь его реализовывать. (Ибо, честно говоря, ценность алгоритма чисто теоретическая. Сложность его оценивается высокой ступенькой экспонент (в русской Википедии написано про экспоненциальную сложность, но это не так: принципиально меньше двухэтажной экспоненты не получить).)

Меня интересует простейший вариант школьных детерминированных задачек. Я почти уверен, что их можно решить *быстро*. Вот, если взять мой прошлый пример про 4-угольник: после того, как я задал AB||CD, то программа, зная, что ординаты точек A и B равны 0, может определить, что ординаты точек C и D равны. После того, как я задам AB=5 и AB=CD, программа поймёт, что разница абсцисс C и D равна 5. И т. д. Я не хочу реализовывать *общий* алгоритм, но реализовать частности (типа указанных выше простейших умозаключений). *Любую* задачу так не решить, но добрую половину школьных геом. задачек — запросто.

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

toady2 ()
Ответ на: комментарий от toady2

Хорошо, но только если вы примерно представляете логику этих частных решений - т.е. как перейти от набора частично определённых фигур и набора условий к следующему набору фигур уже более определённому, потом добавить ещё условие и т.д. Я могу представить как решать любые логические задачи (выше было), но как решать в числах - не очень представляю.

Тут было о четырёх пунктах реализации (и тут соответствующий код). Нужно пойти дальше:

5) Мы хотим, чтобы фигуры могли иметь неопределённые элементы. Поэтому вместо векторного пространства (и соответственно точек и других фигур) над полем Float мы делаем векторное пространство и геометрию над полем (Either (Undefined ...) f) (имеется в виду Data.Either), т.е. в качестве «правых» значений у нас обычные, определённые, элементы, а в качестве «левых» - неопределённые (там может быть что угодно). Конечно, нужно ещё сделать это полем - написать instance Either для класса Num, так чтобы основные функции работали. И остальные функции писать в расчёте на это - короче говоря, для правых значений (когда всё известно) будет считаться по обычным правилам, а для левых я не знаю что нужно делать, наверно ничего - это те самые случаи когда какие-то элементы не известны.

6) Написать функцию, схематически:

geomEval :: [Figure] -> [Relation] -> IO ([Figure])

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

quasimoto ★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.