haskell - How to make Vect n Int an instance of Monoid -

haskell - How to make Vect n Int an instance of Monoid -

in idris, vect n a datatype representing vector of n length containing items of type a. imagine have function:

foo : int -> vect 4 int foo n = [n-1, n, n+1, n*4]

the body of function not important, returns vector of 4 ints. now, want utilize function concatmap follows:

bar : vect n int -> vect (4*n) int bar vals = concatmap foo vals

bar function takes int vector of length n , returns ones of length 4*n.

the type signature of concatmap is:

prelude.foldable.concatmap : foldable t => monoid m => (a -> m) -> t -> m

and hence if seek compile bar, error:

when elaborating right hand side of bar: can't resolve type class monoid (vect (plus n (plus n (plus n (plus n 0)))) int)

this means vect n int isn't instance of monoid. create instance of monoid, need implement:

prelude.algebra.neutral : monoid =>

unfortunately i'm not sure how this. list implements monoid, follows:

instance monoid (list a) neutral = []

but if seek implement monoid neutral = [] vect n int, receive error:

when elaborating right hand side of prelude.algebra.vect n int instance of prelude.algebra.monoid, method neutral: | can't unify | vect 0 int | | vect n int | | specifically: | can't unify | 0 | | n

so wondering, how go implementing monoid vect?

you can't implement monoid such able write downwards look using concatmap. think signature of concatmap:

(foldable t, monoid m) => (a -> m) -> t -> m

note m must the same monoid in both homecoming type of functional argument (a -> m) , homecoming type of whole function. this not case vect n a. consider expression:

concatmap foo vals

here foo have type of a -> vect 4 a, , result of concatmap want of type vect (4*n) a n length of original vector. cannot fit concatmap type because have application of concatmap requires type like:

(foldable t, monoid m, monoid m1) => (a -> m) -> t -> m1

where result monoid , value returned function can different types, while concatmap imposes utilize same type.

[a] , vect n a different because [] not include length in type, , allows write concatmap function. in fact allows create monoid instance [] , concatenation binary operator.

when start attaching length type possibility vanishes because cannot mix different lengths anymore , vect n a not form monoid concatenation. concatenation operator becomes of type a -> b -> c in general case, , in particular it's type vects vect n -> vect m -> vect (n+m) a, different type lists: [a] -> [a] ->[a].

this said, error reported due fact when writing instance monoid class of vect n a value of neutral must of type vect n a [] of type vect 0 a.

however can create different instance monoid type class on vect n a. if elements of such vector monoids can create monoid of such vectors.

in case neutral vector must of length n, , sensible value can give elements neutral of elements monoid. want neutral of vect n a replicate n neutral.

the binary operation monoid element-wise application of operation between elements.

so instance like:

instance monoid => monoid (vect n a) neutral = replicate n neutral instance semigroup => semigroup (vect n a) nil <+> nil = nil (x :: xs) <+> (y :: ys) = (x <+> y) :: (xs <+> ys)

unfortunately i'm not idris user/programmer can't tell how correctly write such code. above haskell-like pseudocode give thought of concepts.

haskell types functional-programming dependent-type idris