LINUX.ORG.RU

Template haskell. Я не совсем понимат!

 , , ,


0

3

Решил тут заняться преждевременными оптимизациями. Очень часто во всяких численных методах используется конструкция вида:

f(x,y)=\sum_{i,j}{a_{x+i,y+j} p_{i,j}}, где a - сетка значений какой-то величины, p - константная матрица. И эта сумма обычно находится в самых узких местах программы.

Поскольку p известна заранее (на стадии компиляции), я решил заоптимизировать вычисление таким образом, что сумма не будет проходить по нулевым элементам и не делать умножение на 1 и -1.

Получение нужной функции:

{-# LANGUAGE QuasiQuotes, TemplateHaskell, TypeFamilies #-}
module Module1 where

import Language.Haskell.TH
import Data.VectorSpace

stencil2D :: (Ord b, Num b, VectorSpace a, b ~ Scalar a) => [[b]] -> ((Int,Int)->a) -> (Int, Int) -> a
stencil2D pat get =
    let
        lx = length $ head pat
        ly = length pat
        -- Zip indices and values:
        i = [
                 ((x', y'), a)
                |(xx, y) <- zip pat [0..]
                ,(a, x) <- zip xx [0..]
                ,a /= 0
                ,let x' = x-(lx`div`2)
                ,let y' = y-(lx`div`2)
            ]

        f r0 (r, a)
                | a ==  1 = (^+^)(get $ r^+^r0)
                | a == -1 = (^-^)(get $ r^+^r0)
                | True    = (^+^)(a*^(get $ r^+^r0))
        
        fun r = foldr (\b a->a.(f r b)) id i
    in
        \r -> fun r zeroV

Проверил бегло, вроде работает. Применение её в compile time и проверка:

-- Dummy get function:
fakeGet :: (Int, Int) -> Float
fakeGet _ = 1

foo = $([| stencil2D [[0,1,0],[1,-4,1],[0,1,0]] fakeGet |])

main = print $ foo (1,1)

Вопрос. (Моё знание и понимание template haskell и quasi-quotation на данный момент близко к нулю.) Действительно ли foo раскрутилась в функцию, с 5 операциями + и одним умножением? (zeroV^+^... я потом уберу).

Ну и прошу опытных людей заодно конструктивно поругать мой код в целом.


Ответ на: комментарий от dmitry_malikov

head небезопасный

Точно, вижу.

Вместо let здесь лучше where.

Стараюсь больше let использовать на высоком уровне. Где-то прочитал, что так вроде богоугоднее.

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

Где-то прочитал, что так вроде богоугоднее.

Мусье, они вообще-то не совсем взаимозаменяемы. Но f - то можно вынести, и зачем там guard?

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

не совсем взаимозаменяемы

Не совсем, но как правило. В данном случае разницы нет.

f - то можно вынести, и зачем там guard?

Зачем выносить? Она одноразовая. Насчёт guard не понял: там же разные действия в зависимости от a.

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

Она одноразовая.

В let - взаимно рекурсивные ф-ии, если ф-уя в where - то видно, что она не зависит от контекста let — иногда бывает читабельнее.

разные действия в зависимости от a.

Эм? Три строчки вроде: f r0 (r, 1) = ...

Действительно ли foo раскрутилась в функцию, с 5 операциями + и одним умножением?

В th мало разбираюсь, но тут подумалось: здесь же нужен рекурсивный вид, а то развернет thunk, что стек положит. Не факт, что seq здесь улучшит ситуацию.

Может стоит сначала посмотеть в сторону deforestation (через StreamFusion etc.) и unboxing.

anonymous ()

Действительно ли foo раскрутилась в функцию, с 5 операциями + и одним умножением?

foo раскроется в вызов stencil2D. $([| ... |]) это идентичное преобразование, оно ничего не даёт.

Кстати, правильно определять шаблон в одном модуле:

foo_ :: Q Exp
foo_ = [| stencil2D [[0,1,0],[1,-4,1],[0,1,0]] fakeGet |]

-- > runQ foo_
-- AppE (AppE (VarE M1.stencil2D) (ListE [ListE [LitE (IntegerL 0),LitE (IntegerL 1),LitE (IntegerL 0)],ListE [LitE (IntegerL 1),AppE (VarE GHC.Num.negate) (LitE (IntegerL 4)),LitE (IntegerL 1)],ListE [LitE (IntegerL 0),LitE (IntegerL 1),LitE (IntegerL 0)]])) (VarE M1.fakeGet)

и сплайсить в другом:

foo :: (Int, Int) -> Float
foo = $(foo_)

если посмотреть

ghc-core --no-asm --no-syntax -- -O3 Module2.hs | less

то можно увидеть что-то вроде

M2.foo =
  M1.$wstencil2D
    @ (M1.Scalar Float)
    @ Float
    M2.foo17
    M2.foo16
    (Eq#
       @ *
       @ (M1.Scalar Float)
       @ (M1.Scalar Float)
       @~ <M1.Scalar Float>)
    M2.foo1

Если ты хочешь вычислять в compile-time, то сама stencil2D должна выражаться через сплайс $() функции типа :: типы-параметров-известных-во-время-компиляции -> Q Exp, то есть функции которая строит правильное AST для функции stencil2D. Это AST превращается в нормальную функцию посредством сплайса $(), само AST можно строить как вручную с помощью конструкторов Exp, с помощью разных вспомогательных функций, с помощью шаблонов [||] со сплайсами $(), ну и всё это делать в монаде Q.

quasimoto ★★★★ ()

А с этим хаскеллом работу то можно найти или все очень печально?

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

$([| ... |]) это идентичное преобразование

Из-за подозрения, что это так, я и создал тред. Вот беда-то.

Если ты хочешь вычислять в compile-time, то сама stencil2D должна выражаться через сплайс $()

Сначала я так и пытался делать, но наткнулся на проблему, что это работает:

Prelude> let f a = [| \x-> abs x |]
Prelude> $(f abs) 1
1

А вот это - нет:

Prelude> let f  a = [| \x-> a x |]

<interactive>:4:24:
    No instance for (Language.Haskell.TH.Syntax.Lift (t1 -> t0))
      arising from a use of `a'
    Possible fix:
      add an instance declaration for
      (Language.Haskell.TH.Syntax.Lift (t1 -> t0))
    In the expression: a x
    In the Template Haskell quotation [| \ x -> a x |]
    In the expression: [| \ x -> a x |]

Видимо потому, что a в compile time не известно (?). Задание сигнатуры f тут не помогает.

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

Эм? Три строчки вроде: f r0 (r, 1) = ...

В чём разница, делать это через pattern matching или guards? Вроде не должно быть особой.

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

Простейший пример:

{-# LANGUAGE TemplateHaskell #-}

module M1 where

import Language.Haskell.TH

data FooType = Sum | Prod

buildFoo :: FooType -> Int -> Q Exp
buildFoo Sum k = [| \x -> x + k |]
buildFoo Prod k = [| \x -> x * k |]
{-# LANGUAGE TemplateHaskell #-}

module M2 where

import M1

fooSum :: Int -> Int
fooSum = $(buildFoo Sum 10)

fooProd :: Int -> Int
fooProd = $(buildFoo Prod 20)

-- > fooSum 2
-- 12
-- > fooProd 3
-- 60
M2.fooSum =
  \ (x_a1el :: Int) ->
    case x_a1el of _ { I# x1_a1et ->
    I# (+# x1_a1et 10)
    }

M2.fooProd =
  \ (x_a1ee :: Int) ->
    case x_a1ee of _ { I# x1_a1eD ->
    I# (*# x1_a1eD 20)
    }

то есть мы пишем отображение из compile-time данных в AST в виде buildSomeFunction (тут кодом пишется код - в лучшем случае можно обойтись красивыми [||] и $(), в худшем - возится с Q и Exp) и заставляем нужный код сгенерироваться из этого AST с помощью someFunction = $(buildSomeFunction myCompileTimeData ... ).

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

Может стоит сначала посмотеть в сторону deforestation (через StreamFusion etc.) и unboxing.

Это уже зависит от конкретного get, я полагаю? В любом случае, я это делаю скорее, чтобы разобраться, а не от нужды какой-то особой.

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

Это-то вроде более-менее понятно. Всякие простые функции для работы с кортежами произвольной длины у меня даже получались, когда я вручную вбивал AST.

Не могу понять, чем плохо вот это: let f a = [| \x-> a x |]

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

Не могу понять, чем плохо вот это: let f a = [| \x-> a x |]

buildFoo :: Q Exp -> Q Exp
buildFoo f = [| \x -> $f x |]

foo :: Int -> Int
foo = $(buildFoo [| abs |])
quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

Спасибо за пример. Теперь вроде ясно, как дальше.

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

Собственно, почему - из Int, (Int, Int) и т.п. можно легко построить AST, как построить AST из (a -> b) не вполне понятно, тут нужен доступ к исходникам функции по имени - проще передать функции сразу закавыченной.

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

А с этим хаскеллом работу то можно найти или все очень печально?

cabal info shpider -> An example: ...

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

а не от нужды какой-то особой.

Уже видно.

anonymous ()

Итак, я позорно отступаю перед этой задачкой до следующего просветления. Остановился на чём-то таком (не компилируется):

stencil2D get pat =
    let
        lx = length $ head pat
        ly = length pat
        -- Zip indices and values:
        i = [
                 ((x', y'), a)
                |(xx, y) <- zip pat [0..]
                ,(a, x) <- zip xx [0..]
                ,a /= 0
                ,let x' = x-(lx`div`2)
                ,let y' = y-(lx`div`2)
            ]

        f ::  ((Int, Int), Float) -> Q Exp
        f (r, a)
                | a ==  1 = [| \r0 -> (^+^)($get $ r^+^r0) |]
                | a == -1 = [| \r0 -> (^-^)($get $ r^+^r0) |]
                | True    = [| \r0 -> (^+^)(a*^($get $ r^+^r0)) |]
        
        dot g i = [| \r -> $g . ($(f i) r) |]
    in 
        foldl dot [|zeroV|] i

Если вкратце, то с таким подходом возникают неприятные проблемы на стыке с расширением TypeFamilies.

Возвращаясь к методу из 0-го поста, если я со включенными оптимизациями сделаю так:

foo = stencil2D [[1,-2,1]] someGet -- Всё известно в compile time

Не выведет ли ghc функцию foo в compile time сам? Вывод ghc-core я что-то пока с трудом разбираю.

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

А с этим хаскеллом работу то можно найти или все очень печально?

Не знаю насчет «найти», но вот создать себе работу точно можно.

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

Кстати, о странностях:

Prelude Language.Haskell.TH> let f::Int->Q Exp; f a = [|a|]
Prelude Language.Haskell.TH>

но

Prelude Language.Haskell.TH> let f::Float->Q Exp; f a = [|a|]

<interactive>:22:30:
    No instance for (Language.Haskell.TH.Syntax.Lift Float)
      arising from a use of `a'
    Possible fix:
      add an instance declaration for
      (Language.Haskell.TH.Syntax.Lift Float)
    In the Template Haskell quotation [| a |]
    In the expression: [| a |]
    In an equation for `f': f a = [| a |]

Вот ghc привереда!

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

Вот ghc привереда!

Там какая-то ерунда с unlifted types - плавающие числа кодируются как рациональные на уровне литералов (Lit), что разумно, но сплайс возвращает небоксированные Float#/Double#, видимо, чтобы оставить возможность оптимизаций (хотя для обычных чисел он так не делает), поэтому их нужно боксировать вручную:

import Language.Haskell.TH.Syntax

instance Lift Float where
  lift = return . LitE . FloatPrimL . toRational

instance Lift Double where
  lift = return . LitE . DoublePrimL . toRational

instance Lift Rational where
  lift = return . LitE . RationalL 

----

t :: Float -> Q Exp
t a = [| a |]

----

{-# LANGUAGE MagicHash #-}

import GHC.Types

foo :: Float
foo = F# $(t 0.11)
quasimoto ★★★★ ()
Ответ на: комментарий от dmfd

Итак, я позорно отступаю перед этой задачкой до следующего просветления

Было бы намного проще, если бы изложение было более замкнутым :) Что там в Data.VectorSpace, например? Может можно сделать так, что TypeFamilies (равенство типов, как я понимаю) вообще не понадобятся?

Не выведет ли ghc функцию foo в compile time сам?

{-# INLINE stencil2D #-}, {-# INLINE someGet #-} и {-# SPECIALIZE stencil2D :: неполиморфный тип #-} могут оказать некий эффект. Но это нужно смотреть. Ещё есть RULES, но их тут, вроде бы, негде применить.

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

Ещё пара примеров. Берем такую вариацию foldl', отдающую свёртке ещё индекс элемента:

loop :: r -> [e] -> (Int -> e -> r -> r) -> r
loop z xs f = go 0 z xs where
  go _ a [] = a
  go i a (e:es) = let a' = f i e a in a' `seq` go (i + 1) a' es

Дальше циклы можно раскрутить довольно просто. Цикл по списку:

unroll1 :: Int -> [Int] -> Q Exp {- [Int] -> Int -}
unroll1 z ps =
    [|
        \ys -> $(
            loop [| z |] ps $
                \i e a -> if e /= 0 then [| ys !! i * e + $a |] else a
        )
    |]

Два вложенных цикла:

unroll2 :: Int -> [[Int]] -> Q Exp {- [[Int]] -> Int -}
unroll2 z ys =
    [|
        \zs -> $(
            loop [| z |] ys $
                \i xs a -> loop a xs $
                    \j e b -> if e /= 0 then [| zs !! i !! j * e + $b |] else b
        )
    |]

Смотрим, что оно генерирует:

vec :: [Int]
vec =  [2, 0, 4, 0]

-- > ppr <$> runQ (unroll1 0 vec)
-- \ys_0 -> ((ys_0 GHC.List.!! 2) GHC.Num.* 4) GHC.Num.+ (((ys_0 GHC.List.!! 0) GHC.Num.* 2) GHC.Num.+ 0)

mtx :: [[Int]]
mtx = [[2, 0, 0, 0],
       [0, 4, 0, 0],
       [0, 0, 8, 0],
       [0, 0, 0, 16]]

-- > ppr <$> runQ (unroll2 0 mtx)
-- \zs_0 -> (((zs_0 GHC.List.!! 3) GHC.List.!! 3) GHC.Num.* 16) GHC.Num.+ ((((zs_0 GHC.List.!! 2) GHC.List.!! 2) GHC.Num.* 8) GHC.Num.+ ((((zs_0 GHC.List.!! 1) GHC.List.!! 1) GHC.Num.* 4) GHC.Num.+ ((((zs_0 GHC.List.!! 0) GHC.List.!! 0) GHC.Num.* 2) GHC.Num.+ 0)))

Генерируем функции так:

unrolled1 :: [Int] -> Int
unrolled1 = $(unroll1 0 vec)

-- > unrolled1 [1 .. 4]
-- 14

unrolled2 :: [[Int]] -> Int
unrolled2 = $(unroll2 0 mtx)

-- > unrolled2 [[1 .. 4], [5 .. 8], [9 .. 12], [13 .. 16]]
-- 370

core и assembler будут соответствующие. Только правда, что это очень преждевременная оптимизация - лучше делать строгость/unpack/inline/speialize/rules и смотреть на core. Но по крайней мере, так можно делать - в каких-то случаях будет полезно.

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

Что там в Data.VectorSpace, например?

Посмотрел. Может, в Prelude и не самая лучшая иерархия классов, но не вижу необходимости писать свои и не использовать Num / Fractional. Если говорить про алгебраические классы - в хаскеле невыразима их аксиоматика (по крайней мере, лучше не пробовать её выражать), поэтому, например, магма и полугруппа неотличимы. Различимые структуры это:

                 Set (Type)
                /   \
           (*) /     \ (+)
              /       \
           MulMag    AddMag
             |         |
           1 |         | 0
             |         |
           MulMon    AddMon
             |         |
  (/), recip |         | (-), negate
             |         |
           MulGrp    AddGrp

Num даёт аддитивную группу и мультипликативный моноид, Fractional достраивает мультипликативную группу, Num + Fractional = Field. Векторы при этом ведут себя как элементы аддитивной группы, так что им тоже можно написать инстанс Num - тогда нулевые векторы будут обозначаться просто как 0, векторы единиц - 1, складывать и вычитать векторы можно будет обычными (+) и (-), ну и так далее (остальные функции Num можно без всякого вреда утилизировать).

Второй вопрос - представлять связь векторное пространство ~ поле мульти-параметрическим классом или одно-параметрическим с семейством типа внутри.

Третий вопрос - как представлять конкретные векторы. Можно делать это кортежами (два, три, четыре элемента, ... - куча бойлерплейта). Можно с помощью списков (но вектора в списках это немного расточительно) или массивов (Data.Vector.Unboxed, например). Во втором случае нужно решить, как 0 типа «Массив» будет превращаться в [0, 0, ...], то есть откуда брать количество элементов (в случае кортежей это понятно).

Пример:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances
  , UndecidableInstances, ScopedTypeVariables, FlexibleContexts, Rank2Types
  , TypeOperators #-}

import Data.TypeLevel.Num.Sets
import Data.TypeLevel.Num.Reps
import qualified Data.Vector.Generic as V
import qualified Data.Vector.Unboxed as UV

infixl 8 *.

class VectorSpace s f | s -> f where
  (*.) :: f -> s -> s

-- * Tuples.

instance (Num a, Num b) => Num (a, b) where
  (x, y) + (x', y') = (x + x', y + y')
  (x, y) * (x', y') = (x * x', y * y')
  (x, y) - (x', y') = (x - x', y - y')
  abs (x, y) = (abs x, abs y)
  signum (x, y) = (signum x, signum y)
  fromInteger n = (fromInteger n, fromInteger n)

instance Num a => VectorSpace (a, a) a where
  k *. (x, y) = (k * x, k * y)

-- (a, b, c), (a, b, c, d), ...

-- * Pure unboxed vectors.

instance (Num a, V.Vector UV.Vector a) => Num (UV.Vector a) where
  (+) = V.zipWith (+)
  (-) = V.zipWith (-)
  (*) = V.zipWith (*)
  abs = V.map abs
  signum = V.map signum
  fromInteger = V.replicate 1 . fromInteger

instance (Num a, V.Vector UV.Vector a) => VectorSpace (UV.Vector a) a where
  (*.) k = V.map (* k)

-- * Subtypes.

class t :> t' | t -> t' where
  sub :: t -> t'
  sup :: t' -> t
  -- t :> t
  -- a :> b, b :> c => a :> c
  -- Top :> a
  -- a : A, B :> A => a : B
  lift :: (t -> t) -> t' -> t'
  lift f = sub . f . sup
  lift2 :: (t -> t -> t) -> t' -> t' -> t'
  lift2 f x y = sub $ f (sup x) (sup y)

-- * Type indexed vectors.

newtype I i t = I { unI :: t } deriving ( Show, Eq )

instance t :> I i t where
  sub = I
  sup = unI

instance (Num a, Nat i, V.Vector v a) => Num (I i (v a)) where
  (+) = lift2 $ V.zipWith (+)
  (-) = lift2 $ V.zipWith (-)
  (*) = lift2 $ V.zipWith (*) 
  abs = lift $ V.map abs
  signum = lift $ V.map signum
  fromInteger = sub . V.replicate (toInt (undefined :: i)) . fromInteger

instance (Num a, V.Vector v a) => VectorSpace (I i (v a)) a where
  (*.) k = lift $ V.map (* k)

В случае с кортежами всё просто, только (*.) появляется. Со списками/массивами тоже просто (функции работают через zip/map), числовой литерал превращается в синглтон. В случае со списками/массивами в I строковые литералы превращаются в вектор размер которого берётся из типа I, например:

type UV i a = V.Vector UV.Vector a => I i (UV.Vector a)

type V4 a = UV D4 a

v4 :: [a] -> V4 a
v4 = I . V.fromList

a :: V4 Double
a = 5 *. v4 [1, 2, 3, 4] + v4 [-1, 2, -3, 4] - 0

-- > a
-- I {unI = fromList [4.0,12.0,12.0,24.0]}
quasimoto ★★★★ ()
#include <iostream>
using namespace std;
 
template<int a, int ...b>
struct Foo
{ 
  Foo()
  {
    Foo<b...> foo();
  }
};
 
template<int a, int b>
struct Foo<a,b>
{ 
  Foo()
  {
    cout<<a;
  }
};
 
int main()
{
  Foo<1,2,3> foo;
}
prog.cpp:10:13: sorry, unimplemented: cannot expand 'b ...' into a fixed-length argument list

Да что за глупые компиляторы нынче пошли. Делом что ли заняться с горя.

quasimoto, посмотрю твой код вечером.

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

P.S. Можно, конечно, явно указать первым параметром шаблона размер массива, и тогда остановка рекурсии будет происходить просто с помощью специализации по этому аргументу. Но это некрасиво. Или же в c++11 есть ключевое слово, означающее «пустой аргумент шаблона», но я его не нашёл.

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

Да что за глупые компиляторы нынче пошли.

Обновиться до 4.7 нужно. Или взять clang++.

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

В том и ирония, что в арчике gcc свежий:

┌[pts/0: ~]
└% gcc --version                                    
gcc (GCC) 4.7.1
Copyright (C) 2012 Free Software Foundation, Inc.
dmfd ()
Ответ на: комментарий от dmfd
$ clang --version
clang version 2.9 (tags/RELEASE_29/final)
Target: x86_64-redhat-linux-gnu
Thread model: posix

Не очень свежий, но тот код работает.

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

Ладно, по ходу разбирательств понял, что цель в данном случае не оправдывает средства. Умение работать с template haskell и quasi-quotation похоже требует большего знания внутренностей ghc, чем мне хотелось бы приобрести.

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

Идея об AdditiveGroup=Num мне тоже в голову приходила, когда начинал смотреть библиотеку. Но в Data.AdditiveGroup, во-первых, операторы кавайнее, во-вторых, операция (*) из Num для групп по сложению и векторов лишена смысла.

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

Т.е. я мог не мучиться, собирая AST по кусочкам, а сделать что-то вроде

    foo = 
    [|
        \zs -> $( some_code )
    |]

Вот так мне больше нравится.

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

P.S. С новым компилятором можно сделать задачку из нулевого поста на с++11, но действительно в compile time всё будет раскручиваться только для целых, при этом нужно будет написать ручками аж 6 специализаций шаблона, что делать мне just 4 fun лень.

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

AdditiveGroup=Num

Не совсем так - Num = additive group + multiplicative monoid. Т.е. почти field (полный field это Fractional).

операторы кавайнее

А вот мне не нравится. Писать ^+^ вместо обычного перегруженного плюса, зачем? Тут явно дублируется функционал Num. Если хочется как-то выделить векторное сложение, то можно просто написать функцию, <+>, например, или ⊕, учитывая что хаскель умеет unicode.

операция (*) из Num для групп по сложению и векторов лишена смысла

Для векторов - [1,2,3] * [1,2,3] = [1,4,9], например. Как в разных APL-ях. А поле и так должно иметь операцию (*).

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

Num = additive group + multiplicative monoid

Вот так согласен. Кстати, странно, почему суровые хаскеллисты до такого не додумались.

Для векторов - [1,2,3] * [1,2,3] = [1,4,9], например.

Ну, в математическом определении векторного пространства никакой операции (*) :: VectorSpace a => a->a->a просто нет. А покомпонентное произведение векторов - это какая-то экзотика, которая порождает новую математическую сущность, сходу не могу даже придумать, где такое применяется.

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

А поле и так должно иметь операцию

Так векторное пространство - само по себе не поле, оно только строится над полем, или я не понял, о чём речь.

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

Вот так согласен.

И additive group + multiplicative monoid это не что иное как кольцо.

Кстати, странно, почему суровые хаскеллисты до такого не додумались.

Общеизвестно, что алгебраические и категорные классы в стандартном хаскеле написаны неправильно. На hackage есть с десяток, если не больше, пакетов реализующих альтернативную Prelude. На Haskell' есть предложение по более правильным числовым классам. В typeclassopedia были описаны (и реализованы в category-extras, правда, план явно перевыполнили) правильные категорные классы не приводящие к ситуации с restricted monads (не позволяющими легко написать некоторые инстансы, к Data.Set например).

Должно быть примерно так:

AddtitiveMagma (+) => AdditiveMonoid (0) => AdditiveGroup((-) / negate)
MultiplicativeMagma (*) => MultiplicativeMonoid (1) => MultiplicativeGroup ((/) / recip)
AdditiveGroup + MultiplicativeMonoid => AdditiveRing (fromInteger)
MultiplicativeGroup + AdditiveMonoid => MultiplicativeRing
AdditiveRing => Num (abs, signum)
MultiplicativeGroup + AdditiveGroup => Field (fromRational)
Field => Fractional
AdditiveRing => EuclideanDomain (div, mod, normalize) => Integral (toInteger)

и

Functor (map) => Pointed (return) => Applicative (<*>) => Monad ((>>=) / join) => MonadPlus (mzero, mplus)
                                                                               => MonadFix (mfix)
                                                                               => MonadZip (mzip)
                                                       => Alternative (empty, <|>)

сходу не могу даже придумать, где такое применяется.

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

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

или я не понял, о чём речь.

Я про то, что проще написать Num и Fractional для поля и Num для пространства - во втором случае будут лишние операции, но их можно совершать просто покомпонентно. Проще написания альтернативных классов (пусть чинят классы в стандарте).

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

[| \zs -> $( some_code ) |]

Примерно так, да - [| \zs -> $( какая-нибудь рекурсивная свёртка собирающая [| ... x ..., где x - liftящиеся значения, ... $acc ..., где acc - уже собранный код типа Q Exp |] ) |].

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

но их можно совершать просто покомпонентно

А если вектора - функции?

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

На Haskell' есть предложение по более правильным числовым классам.

Вот тогда все остальные языки станут ненужны! (шутка) Кстати, есть некая CAL «Axiom», в которой система типов якобы хорошо описывает абстрактную алгебру. Из-за совершенно не эстетичного синтаксиса я на неё пока не смотрел, как там дела не в курсе?

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

А если вектора - функции?

Если функции из множества в поле, то

instance Num b => Num (a -> b) where
  (f + g) x = f x + g x
  (f * g) x = f x * g x
  abs = (abs .)
  signum = (signum .)
  fromInteger = const . fromInteger

instance Num b => VectorSpace (a -> b) b where
  (*.) k = ((k *) .)
quasimoto ★★★★ ()
Ответ на: комментарий от dmfd

как там дела не в курсе?

Не смотрел, но судя по

In Axiom, all objects have a type. Examples of types are mathematical structures (such as rings, fields, polynomials) as well as data structures from computer science (e.g., lists, trees, hash tables).

и

A function can take a type as argument, and its return value can also be a type.

похоже на велосипед à la зависимые типы. В Agde непосредственно данные (числа, деревья, функции) и математические структуры (группы, кольца, поля) фактически ничем не отличаются - их можно определить как обычные данные (data) и записи (record). Сложные данные обычно определяются как data (с разными конструкторами ), математические структуры - как record, т.е. как модуль с одним конструктором для типа данных в который складываются теоремы (как функции с зависимыми типами). Соответственно, вместо классов типов и их иерархий там обычные записи с теоремами и их агрегация. Ad-hoc полиморфизм при этом - чисто технический момент (instance arguments).

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