Extensible states

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
24 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Extensible states

Alberto G. Corona
Hi,

Anyone used some of the extensible record packages to create a kind of extensible state monad?

I mean something that besides having "get", "gets" and "put"  would have some kind of "add" and "gets":

add :: a -> State ()
gets  :: State (Maybe a)

or 

add :: LabelName -> a -> State ()
gets :: LabelName -> State (Maybe a)


So that I can extend the state without using additional monad transformers. Monad transformers are very hard for beginners and scramble error messages

I did the first option for MFlow, hplayground and Transient packages (setSData and getSData). But my solution uses a map indexed by type and this requires a lookup for each access.

I would like to know if there is an alternative with no lookups. I´m not obsessed with speed but In some applications the speed may be important....

Anyone?
--
Alberto.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Roman Cheplyaka-2
On 05/05/15 12:40, Alberto G. Corona  wrote:

> Hi,
>
> Anyone used some of the extensible record packages to create a kind of
> extensible state monad?
>
> I mean something that besides having "get", "gets" and "put"  would have
> some kind of "add" and "gets":
>
> add :: a -> State ()
> gets  :: State (Maybe a)
>
> or
>
> add :: LabelName -> a -> State ()
> gets :: LabelName -> State (Maybe a)
>
>
> So that I can extend the state without using additional monad
> transformers. Monad transformers are very hard for beginners and
> scramble error messages
>
> I did the first option for MFlow, hplayground and Transient packages
> (setSData and getSData). But my solution uses a map indexed by type and
> this requires a lookup for each access.
>
> I would like to know if there is an alternative with no lookups. I´m not
> obsessed with speed but In some applications the speed may be important....
>
> Anyone?

If you care about the error message quality, you'd rather stay away from
extensible records.

And if you care about speed, most (all?) extensible records give you
O(n) access, so you'd be actually better off with a simple (Hash)Map.

Roman


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Adam Vogt
On Tue, May 5, 2015 at 5:50 AM, Roman Cheplyaka <[hidden email]> wrote:
> And if you care about speed, most (all?) extensible records give you
> O(n) access, so you'd be actually better off with a simple (Hash)Map.
>
> Roman

https://github.com/fumieval/extensible is an example that is log n lookup, but it's not really clear (to me) that it would be faster for a real program since you might have small records only, and maybe other operations are slower.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Marcin Mrotek
Hello,

I'm not sure if this is what you're looking for, but vinyl + lens state monad combinators let you write something like this:

foo :: State (Rec Foo [B,C,F]) Bar
foo = ...

bar = State (Rec Foo [A,B,C,D,E,F]
bar = do
   ...
   x <- zoom rsubset foo
   ...
   rlens SA .= 3
   ...

Unfortunately Vinyl has O(n) lookup (unless it gets optimized away by sufficiently glorious haskell compiler, I guess, but I have no idea whether it actually can happen). But I'm not sure if the speed impact is noticeable, compared to using monad transformer stacks, for example.


Best regards,
Marcin Mrotek

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Alberto G. Corona
Thanks all of you.

So there is no trick that can make extensible records O(1) for field access, like the native haskell records?. I didn´t know that all the extensible records have  O(n) or O(log n) at most.

That is not better than my State monad with a Data.Map.  It is not possible to use HList-like records like the one that Adam mentioned since the type signature must not change when a new field is added.

2015-05-05 22:20 GMT+02:00 Marcin Mrotek <[hidden email]>:
Hello,

I'm not sure if this is what you're looking for, but vinyl + lens state monad combinators let you write something like this:

foo :: State (Rec Foo [B,C,F]) Bar
foo = ...

bar = State (Rec Foo [A,B,C,D,E,F]
bar = do
   ...
   x <- zoom rsubset foo
   ...
   rlens SA .= 3
   ...

Unfortunately Vinyl has O(n) lookup (unless it gets optimized away by sufficiently glorious haskell compiler, I guess, but I have no idea whether it actually can happen). But I'm not sure if the speed impact is noticeable, compared to using monad transformer stacks, for example.


Best regards,
Marcin Mrotek

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe




--
Alberto.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

ODP: Extensible states

Marcin Mrotek
I think that the whole point of extensible records is to change the type on appending, to provide more safety at compile time than (hash) maps. If you don't want to use lenses (zoom) to combine different state monads, I guess a map is the best option.

Kind regards,
Marcin Mrotek

Od: [hidden email]
Wysłano: ‎2015-‎05-‎05 23:03
Do: [hidden email]
DW: [hidden email]; [hidden email]
Temat: Re: [Haskell-cafe] Extensible states

Thanks all of you.

So there is no trick that can make extensible records O(1) for field access, like the native haskell records?. I didn´t know that all the extensible records have  O(n) or O(log n) at most.

That is not better than my State monad with a Data.Map.  It is not possible to use HList-like records like the one that Adam mentioned since the type signature must not change when a new field is added.

2015-05-05 22:20 GMT+02:00 Marcin Mrotek <[hidden email]>:
Hello,

I'm not sure if this is what you're looking for, but vinyl + lens state monad combinators let you write something like this:

foo :: State (Rec Foo [B,C,F]) Bar
foo = ...

bar = State (Rec Foo [A,B,C,D,E,F]
bar = do
   ...
   x <- zoom rsubset foo
   ...
   rlens SA .= 3
   ...

Unfortunately Vinyl has O(n) lookup (unless it gets optimized away by sufficiently glorious haskell compiler, I guess, but I have no idea whether it actually can happen). But I'm not sure if the speed impact is noticeable, compared to using monad transformer stacks, for example.


Best regards,
Marcin Mrotek

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe




--
Alberto.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Marcin Mrotek
Just as an afterthought about the O(n) lookup issue - extensible
records are dependently typed versions of old, well-known data
structures, so you always have a trade off between lookup and
appending. In Haskell it's relatively easy to implement dependently
typed lists (Vinyl, HList, etc), or maps (?) (apparently, Extensible
linked by Adam, but I admit I haven't looked into the code).
Dependently typed arrays are trickier. I guess it could be, for
example, hacked around a (Vector Dynamic), then using (fromJust .
fromDynamic) when it's certain at compile time that a there's a value
of a certain type hidden in there, but I'm not sure if anyone has
actually implemented it. They would necessarily have O(n) append,
though.

Best regards,
Marcin Mrotek
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Alexey Khudyakov
In reply to this post by Alberto G. Corona
On 6 May 2015 at 00:03, Alberto G. Corona <[hidden email]> wrote:
> Thanks all of you.
>
> So there is no trick that can make extensible records O(1) for field access,
> like the native haskell records?. I didn´t know that all the extensible
> records have  O(n) or O(log n) at most.
>
In principle it's possible to get O(1) access for extensible records. It depends
on how undelying data layout. It's obviously not possible to have O(1) if
record is build from ordinary ADT but if if record internally is array it is
possible. Of course downside is appending is O(n) in that case
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Marcos Viera
In reply to this post by Roman Cheplyaka-2
In the following paper we introduced an implementation that performs lookup in O(log n) and insertion in O(1) by moving some of the work to compile time.

@INPROCEEDINGS { MVP13,
    AUTHOR = { Martinez, Bruno and Viera, Marcos and Pardo, Alberto },
    TITLE = { Just Do It While Compiling!: Fast Extensible Records in Haskell },
    BOOKTITLE = { Proceedings of the ACM SIGPLAN 2013 Workshop on Partial Evaluation and Program Manipulation },
    SERIES = { PEPM '13 },
    YEAR = { 2013 },
    ISBN = { 978-1-4503-1842-6 },
    LOCATION = { Rome, Italy },
    PAGES = { 77--86 },
    NUMPAGES = { 10 },
    DOI = { 10.1145/2426890.2426908 },
    ACMID = { 2426908 },
    PUBLISHER = { ACM },
    ADDRESS = { New York, NY, USA },
    KEYWORDS = { balanced trees, extensible records, haskell, hlist, staged computation, type-level programming },
    PDF = { http://www.fing.edu.uy/~mviera/papers/pepm13.pdf },
}

Best,
 marcos




On Tue, May 5, 2015 at 6:50 AM, Roman Cheplyaka <[hidden email]> wrote:
On 05/05/15 12:40, Alberto G. Corona  wrote:
> Hi,
>
> Anyone used some of the extensible record packages to create a kind of
> extensible state monad?
>
> I mean something that besides having "get", "gets" and "put"  would have
> some kind of "add" and "gets":
>
> add :: a -> State ()
> gets  :: State (Maybe a)
>
> or
>
> add :: LabelName -> a -> State ()
> gets :: LabelName -> State (Maybe a)
>
>
> So that I can extend the state without using additional monad
> transformers. Monad transformers are very hard for beginners and
> scramble error messages
>
> I did the first option for MFlow, hplayground and Transient packages
> (setSData and getSData). But my solution uses a map indexed by type and
> this requires a lookup for each access.
>
> I would like to know if there is an alternative with no lookups. I´m not
> obsessed with speed but In some applications the speed may be important....
>
> Anyone?


If you care about the error message quality, you'd rather stay away from
extensible records.

And if you care about speed, most (all?) extensible records give you
O(n) access, so you'd be actually better off with a simple (Hash)Map.

Roman


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Adam Vogt
In reply to this post by Marcin Mrotek

I think there are many cases where some standard data type (that is not a list) is paired with type-level lists:

I've tried the (unboxed) array case with http://code.haskell.org/HList/Data/HList/broken/RecordU.hs (worked with ghc 7.8), but it didn't seem to be any faster in my tests: I have a feeling that the index into the array should not be calculated as 1+1+1+1: the author of extensible does something that looks better.

CTRex https://github.com/atzeus/CTRex does that dynamic+hash map idea.

Another example is https://github.com/nikita-volkov/record using one data type for each length supported

Just as an afterthought about the O(n) lookup issue - extensible
records are dependently typed versions of old, well-known data
structures, so you always have a trade off between lookup and
appending. In Haskell it's relatively easy to implement dependently
typed lists (Vinyl, HList, etc), or maps (?) (apparently, Extensible
linked by Adam, but I admit I haven't looked into the code).
Dependently typed arrays are trickier. I guess it could be, for
example, hacked around a (Vector Dynamic), then using (fromJust .
fromDynamic) when it's certain at compile time that a there's a value
of a certain type hidden in there, but I'm not sure if anyone has
actually implemented it. They would necessarily have O(n) append,
though.

Best regards,
Marcin Mrotek

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Marcin Mrotek
Okay, perhaps I'm too newbie to understand the big picture, but it
seems to me you can get either:

a) O(1) access to any, arbitrarily selected (at runtime) field
b) O(1) append

I guess option a) is better performance-wise, as appending is usually
done less often than selecting (an O(1) slice is already possible with
independently typed regular Haskell records) but
dependently-typed-list-based implementation, or at the very least
Vinyl (I haven't ever used HList) has the advantage of being dead
simple in both implementation and usage. I mean, with Vinyl, you can
write manual recursion over Rec's like:

foo :: Rec ... -> Rec ...
foo RNil = ...
foo (r :& rs) = ...

whenever GHC's typechecker gives up and goes on a strike; and I dare
to say, with commonly used record sizes (have you ever used a record
with more than, let's say, 10 fields?) the speed tradeoff is not
noticeable.

Don't get me wrong, I'm all in for cutting edge solutions like the one
mentioned by Marcos, but I do think that rejecting the existing ones
based on the non-constant time lookup is just premature optimisation.

Best regards,
Marcin Mrotek
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Marcin Mrotek
Sorry, I meant:

*O(1) slicing is already possible with
independently typed regular Haskell VECTORS

Best regards,
Marcin Mrotek
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Fumiaki Kinoshita
In reply to this post by Alberto G. Corona
Except the performance, my extensible[0] library provides native lens support (label names are also lenses!) and quite easy to use. Let me show an example:

{-# LANGUAGE TypeOperators, DataKinds, TemplateHaskell, FlexibleContexts #-}
import Data.Extensible
import Control.Lens
import Control.Monad.State

mkField "foo bar baz"

statefulStuff :: State (Record '["foo" :> Int, "bar" :> Int, "baz" :> Float]) ()
statefulStuff = do
    v <- use foo
    bar += v
    baz .= 42

main = print $ execState statefulStuff
  $ foo @= 10 <: bar @= 0 <: baz @= 0 <: Nil

I could use Vector Any internally for O(1) lookup, but seems trade-off between lookup and update.

2015-05-05 18:40 GMT+09:00 Alberto G. Corona <[hidden email]>:
Hi,

Anyone used some of the extensible record packages to create a kind of extensible state monad?

I mean something that besides having "get", "gets" and "put"  would have some kind of "add" and "gets":

add :: a -> State ()
gets  :: State (Maybe a)

or 

add :: LabelName -> a -> State ()
gets :: LabelName -> State (Maybe a)


So that I can extend the state without using additional monad transformers. Monad transformers are very hard for beginners and scramble error messages

I did the first option for MFlow, hplayground and Transient packages (setSData and getSData). But my solution uses a map indexed by type and this requires a lookup for each access.

I would like to know if there is an alternative with no lookups. I´m not obsessed with speed but In some applications the speed may be important....

Anyone?
--
Alberto.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Extensible states

Alberto G. Corona
hmmm..

A form of "extensible state" constructed with an state monad with a Map indexed by the type of the data using "typeOf" could have advantages over extensible records. It makes the "transport" of data and the addition of more kinds of data less cumbersome.

 Among other things it encourages good programming practices like the use of newtypes. It is just a matter of defining two primitives:

with getData :: (MonadState TheMap m,Typeable a) => m (Maybe a)

and setData :: (MonadState TheMap m, Typeable a) => a -> m ()

 and perhaps a third : delData.

2015-05-08 7:33 GMT+02:00 Fumiaki Kinoshita <[hidden email]>:
Except the performance, my extensible[0] library provides native lens support (label names are also lenses!) and quite easy to use. Let me show an example:

{-# LANGUAGE TypeOperators, DataKinds, TemplateHaskell, FlexibleContexts #-}
import Data.Extensible
import Control.Lens
import Control.Monad.State

mkField "foo bar baz"

statefulStuff :: State (Record '["foo" :> Int, "bar" :> Int, "baz" :> Float]) ()
statefulStuff = do
    v <- use foo
    bar += v
    baz .= 42

main = print $ execState statefulStuff
  $ foo @= 10 <: bar @= 0 <: baz @= 0 <: Nil

I could use Vector Any internally for O(1) lookup, but seems trade-off between lookup and update.

2015-05-05 18:40 GMT+09:00 Alberto G. Corona <[hidden email]>:
Hi,

Anyone used some of the extensible record packages to create a kind of extensible state monad?

I mean something that besides having "get", "gets" and "put"  would have some kind of "add" and "gets":

add :: a -> State ()
gets  :: State (Maybe a)

or 

add :: LabelName -> a -> State ()
gets :: LabelName -> State (Maybe a)


So that I can extend the state without using additional monad transformers. Monad transformers are very hard for beginners and scramble error messages

I did the first option for MFlow, hplayground and Transient packages (setSData and getSData). But my solution uses a map indexed by type and this requires a lookup for each access.

I would like to know if there is an alternative with no lookups. I´m not obsessed with speed but In some applications the speed may be important....

Anyone?
--
Alberto.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe





--
Alberto.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Efficient records with arbitrarily many fields [was: Extensible states]

Ben Franksen
In reply to this post by Marcin Mrotek
Marcin Mrotek wrote:

> Okay, perhaps I'm too newbie to understand the big picture, but it
> seems to me you can get either:
>
> a) O(1) access to any, arbitrarily selected (at runtime) field
> b) O(1) append
>
> I guess option a) is better performance-wise, as appending is usually
> done less often than selecting (an O(1) slice is already possible with
> independently typed regular Haskell records) but
> dependently-typed-list-based implementation, or at the very least
> Vinyl (I haven't ever used HList) has the advantage of being dead
> simple in both implementation and usage. I mean, with Vinyl, you can
> write manual recursion over Rec's like:
>
> foo :: Rec ... -> Rec ...
> foo RNil = ...
> foo (r :& rs) = ...
>
> whenever GHC's typechecker gives up and goes on a strike; and I dare
> to say, with commonly used record sizes (have you ever used a record
> with more than, let's say, 10 fields?) the speed tradeoff is not
> noticeable.

While more than 10 fields in a record is uncommon for typical library APIs
and simple programs, real world projects can grow much larger records. One
example is configuration data for complex programs (like Darcs or even GHC)
with many options. It would be so nice if we could use record types for the
configuration! Another application could in control system toolkits like
EPICS [1], which currently has (actually: generates) C records with
potentially hundreds of fields.

If lookup is / remains linear we can never efficiently support these kinds
of applications and that would be very sad.

I think the most reasonable default is O(1) for lookup and O(n) for
extension, like in Nikita Volkov's record package. It is quite unfortunate
that this package limits the number of fields! If GHC would offer generic
support for tuples of arbitrary size (with the same efficiency as today)
this limitation could be avoided and all would be well.

Cheers
Ben

[1] http://www.aps.anl.gov/epics/
--
"Make it so they have to reboot after every typo." ― Scott Adams


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Efficient records with arbitrarily many fields [was: Extensible states]

Nikita Volkov-3
I somehow missed the preceding discussion, so I'll comment on what I've seen so far.
 
I think the most reasonable default is O(1) for lookup and O(n) for
extension, like in Nikita Volkov's record package. It is quite unfortunate
that this package limits the number of fields! If GHC would offer generic
support for tuples of arbitrary size (with the same efficiency as today)
this limitation could be avoided and all would be well.

Currently "record" is limited to up to 24 fields. However it was just an arbitrary number that I've chosen. No part of GHC limits us to that number. The only reason I'm not introducing bigger arities is that unfortunately the compilation time of the "record" library grows exponentially in relation to the highest arity supported. I expect, that limitation could be lifted once/if the ideas behind the library get implemented as an extension to GHC.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Fwd: Efficient records with arbitrarily many fields [was: Extensible states]

Alexander V Vershilov
In reply to this post by Ben Franksen
(forgot to reply to cafe list
Hi.

You can take a look at vector-fixed-hetero [1],
that can act as anonymous structure with arbitrary number of fields,
convertion to and from

datatypes with the same structure and many more features. It's missing
field names though
and syntactic sugar that 'records' package have. If you like to
reinvent a wheel, then

you can use following appoach:

introduce some typelevel info

data a :? (b :: Symbol)

data FieldName (t :: Symbol) = FieldName

introduce generic structure for records with any number of fiels

newtype ARec (m :: [*]) = ARec { unRec :: Array Any }
type instance TProxy (ARec m) = m
type instance VProxy (ARec m) = ARec

rerec :: ARec a -> ARec b
rerec = ARec . unRec

indexRec :: (KnownNat (FieldIndex name m), FieldType name m ~ a)
         => proxy name -> ARec m -> a
indexRec name v = unsafeCoerce $
  indexArray (unRec v) (fromIntegral (natVal (indexProxy name v)))

updateRec :: (KnownNat (Length m), KnownNat (FieldIndex name m),
FieldType name m ~ a)
          => proxy name -> a -> ARec m -> ARec m
updateRec name b v = runST $ do
    out <- newArray len undefined
    copyArray out 0 (unRec v) 0 len
    writeArray out idx (unsafeCoerce b)
    ARec <$> unsafeFreezeArray out
  where
    idx = fromIntegral (natVal (indexProxy name v))
    len = fromIntegral (natVal (lengthProxy v))

you'll need some typelevel magic for that:
type family FieldType (n :: Symbol) m where
  FieldType n ((a :? n) ': z) = a
  FieldType n (b ': z)        = FieldType n z

type family FieldIndex (n::Symbol) m :: Nat where
  FieldIndex n ((a :? n) ': z) = 0
  FieldIndex n (   b     ': z) = 1 + FieldIndex n z

indexProxy :: (KnownNat c, FieldIndex n m ~ c) => proxy1 n -> proxy2 m
-> Proxy c
indexProxy _ _ = Proxy

type family Length m where
  Length '[] = 0
  Length (x ': xs) = 1 + Length xs

lengthProxy :: (KnownNat c, Length n ~ c) => proxy n -> Proxy c
lengthProxy _ = Proxy

then you can implement lenses:

instance (KnownNat (FieldIndex n m), KnownNat (Length m), FieldType n m ~ a)
         => HasField (n :: Symbol) (ARec m)  a where
  getField = indexRec
  updateField p = flip (updateRec p)


fieldLens' :: (HasField name z a, FieldType name (TProxy z) ~ a)
           => FieldName name -> Lens z z a a
fieldLens' name = \f m -> fmap (updateField name m)
                               (f $ getField name m)


type family UpdateType (n :: Symbol) z a b where
  UpdateType n ((a :? n) ': z ) a b = (b :? n) ': z
  UpdateType n (   z     ': zs) a b =    z     ': UpdateType n zs a b

fieldLens :: ( ARec m ~ z, ARec m' ~ z', m' ~ UpdateType name m a b
             , FieldType name m  ~ a, FieldType name m' ~ b
             , KnownNat (FieldIndex name m), KnownNat (FieldIndex name m')
             , KnownNat (Length m), KnownNat (Length m')
             ) => FieldName name -> Lens z z' a b
fieldLens name = \f m -> fmap (updateField name (rerec m))
                              (f $ getField name m)

this approach is more or less the same as records package with only one
datastructure and almost the same syntactic sugar can be applied, the

only missing thing is that pattern matching will be more difficult that with

records.

At this point it's not possible to write strict fields, but it can be
easily extended.

If someone is interested in this sort of wheel, I can prepare a package and some

docs about and with coercion with other solutions like
fixed-vector-hetero and records.



[1] https://hackage.haskell.org/package/fixed-vector-hetero


On Sat, Jul 4, 2015, 16:08 Ben Franksen <[hidden email]> wrote:

>
> Marcin Mrotek wrote:
> > Okay, perhaps I'm too newbie to understand the big picture, but it
> > seems to me you can get either:
> >
> > a) O(1) access to any, arbitrarily selected (at runtime) field
> > b) O(1) append
> >
> > I guess option a) is better performance-wise, as appending is usually
> > done less often than selecting (an O(1) slice is already possible with
> > independently typed regular Haskell records) but
> > dependently-typed-list-based implementation, or at the very least
> > Vinyl (I haven't ever used HList) has the advantage of being dead
> > simple in both implementation and usage. I mean, with Vinyl, you can
> > write manual recursion over Rec's like:
> >
> > foo :: Rec ... -> Rec ...
> > foo RNil = ...
> > foo (r :& rs) = ...
> >
> > whenever GHC's typechecker gives up and goes on a strike; and I dare
> > to say, with commonly used record sizes (have you ever used a record
> > with more than, let's say, 10 fields?) the speed tradeoff is not
> > noticeable.
>
> While more than 10 fields in a record is uncommon for typical library APIs
> and simple programs, real world projects can grow much larger records. One
> example is configuration data for complex programs (like Darcs or even GHC)
> with many options. It would be so nice if we could use record types for the
> configuration! Another application could in control system toolkits like
> EPICS [1], which currently has (actually: generates) C records with
> potentially hundreds of fields.
>
> If lookup is / remains linear we can never efficiently support these kinds
> of applications and that would be very sad.
>
> I think the most reasonable default is O(1) for lookup and O(n) for
> extension, like in Nikita Volkov's record package. It is quite unfortunate
> that this package limits the number of fields! If GHC would offer generic
> support for tuples of arbitrary size (with the same efficiency as today)
> this limitation could be avoided and all would be well.
>
> Cheers
> Ben
>
> [1] http://www.aps.anl.gov/epics/
> --
> "Make it so they have to reboot after every typo." ― Scott Adams
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe


--
Alexander
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Efficient records with arbitrarily many fields [was: Extensible states]

Ben Franksen
In reply to this post by Nikita Volkov-3
Nikita Volkov wrote:

> I somehow missed the preceding discussion, so I'll comment on what I've
> seen so far.
>
>> I think the most reasonable default is O(1) for lookup and O(n) for
>> extension, like in Nikita Volkov's record package. It is quite
>> unfortunate that this package limits the number of fields! If GHC would
>> offer generic support for tuples of arbitrary size (with the same
>> efficiency as today) this limitation could be avoided and all would be
>> well.
>
>
> Currently "record" is limited to up to 24 fields. However it was just an
> arbitrary number that I've chosen. No part of GHC limits us to that
> number.
> The only reason I'm not introducing bigger arities is that
> unfortunately the compilation time of the "record" library grows
> exponentially in relation to the highest arity supported. I expect, that
> limitation could be lifted once/if the ideas behind the library get
> implemented as an extension to GHC.

Thanks for the clarification. So there is no hard limit in GHC, but we are
(currently) limited by other factors. Some (more or less) minimal compiler
support is, I guess, necessary to make any of the existing record libraries
practical for real world programs.

Cheers
Ben
--
"Make it so they have to reboot after every typo." ― Scott Adams


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Efficient records with arbitrarily many fields [was: Extensible states]

Ben Franksen
In reply to this post by Alexander V Vershilov
Thanks, I didn't know of vector-fixed-hetero. Quite interesting.

Anyway, I am not so much interested in getting reasonable efficiency from
any of the existing libraries right now, as I am in reaching consensus about
what kind of compiler support would be needed to make any of them practical.

Cheers
Ben

Alexander V Vershilov wrote:

> (forgot to reply to cafe list
> Hi.
>
> You can take a look at vector-fixed-hetero [1],
> that can act as anonymous structure with arbitrary number of fields,
> convertion to and from
>
> datatypes with the same structure and many more features. It's missing
> field names though
> and syntactic sugar that 'records' package have. If you like to
> reinvent a wheel, then
>
> you can use following appoach:
>
> introduce some typelevel info
>
> data a :? (b :: Symbol)
>
> data FieldName (t :: Symbol) = FieldName
>
> introduce generic structure for records with any number of fiels
>
> newtype ARec (m :: [*]) = ARec { unRec :: Array Any }
> type instance TProxy (ARec m) = m
> type instance VProxy (ARec m) = ARec
>
> rerec :: ARec a -> ARec b
> rerec = ARec . unRec
>
> indexRec :: (KnownNat (FieldIndex name m), FieldType name m ~ a)
>          => proxy name -> ARec m -> a
> indexRec name v = unsafeCoerce $
>   indexArray (unRec v) (fromIntegral (natVal (indexProxy name v)))
>
> updateRec :: (KnownNat (Length m), KnownNat (FieldIndex name m),
> FieldType name m ~ a)
>           => proxy name -> a -> ARec m -> ARec m
> updateRec name b v = runST $ do
>     out <- newArray len undefined
>     copyArray out 0 (unRec v) 0 len
>     writeArray out idx (unsafeCoerce b)
>     ARec <$> unsafeFreezeArray out
>   where
>     idx = fromIntegral (natVal (indexProxy name v))
>     len = fromIntegral (natVal (lengthProxy v))
>
> you'll need some typelevel magic for that:
> type family FieldType (n :: Symbol) m where
>   FieldType n ((a :? n) ': z) = a
>   FieldType n (b ': z)        = FieldType n z
>
> type family FieldIndex (n::Symbol) m :: Nat where
>   FieldIndex n ((a :? n) ': z) = 0
>   FieldIndex n (   b     ': z) = 1 + FieldIndex n z
>
> indexProxy :: (KnownNat c, FieldIndex n m ~ c) => proxy1 n -> proxy2 m
> -> Proxy c
> indexProxy _ _ = Proxy
>
> type family Length m where
>   Length '[] = 0
>   Length (x ': xs) = 1 + Length xs
>
> lengthProxy :: (KnownNat c, Length n ~ c) => proxy n -> Proxy c
> lengthProxy _ = Proxy
>
> then you can implement lenses:
>
> instance (KnownNat (FieldIndex n m), KnownNat (Length m), FieldType n m ~
> a)
>          => HasField (n :: Symbol) (ARec m)  a where
>   getField = indexRec
>   updateField p = flip (updateRec p)
>
>
> fieldLens' :: (HasField name z a, FieldType name (TProxy z) ~ a)
>            => FieldName name -> Lens z z a a
> fieldLens' name = \f m -> fmap (updateField name m)
>                                (f $ getField name m)
>
>
> type family UpdateType (n :: Symbol) z a b where
>   UpdateType n ((a :? n) ': z ) a b = (b :? n) ': z
>   UpdateType n (   z     ': zs) a b =    z     ': UpdateType n zs a b
>
> fieldLens :: ( ARec m ~ z, ARec m' ~ z', m' ~ UpdateType name m a b
>              , FieldType name m  ~ a, FieldType name m' ~ b
>              , KnownNat (FieldIndex name m), KnownNat (FieldIndex name m')
>              , KnownNat (Length m), KnownNat (Length m')
>              ) => FieldName name -> Lens z z' a b
> fieldLens name = \f m -> fmap (updateField name (rerec m))
>                               (f $ getField name m)
>
> this approach is more or less the same as records package with only one
> datastructure and almost the same syntactic sugar can be applied, the
>
> only missing thing is that pattern matching will be more difficult that
> with
>
> records.
>
> At this point it's not possible to write strict fields, but it can be
> easily extended.
>
> If someone is interested in this sort of wheel, I can prepare a package
> and some
>
> docs about and with coercion with other solutions like
> fixed-vector-hetero and records.
>
>
>
> [1] https://hackage.haskell.org/package/fixed-vector-hetero
>
>
> On Sat, Jul 4, 2015, 16:08 Ben Franksen <[hidden email]> wrote:
>>
>> Marcin Mrotek wrote:
>> > Okay, perhaps I'm too newbie to understand the big picture, but it
>> > seems to me you can get either:
>> >
>> > a) O(1) access to any, arbitrarily selected (at runtime) field
>> > b) O(1) append
>> >
>> > I guess option a) is better performance-wise, as appending is usually
>> > done less often than selecting (an O(1) slice is already possible with
>> > independently typed regular Haskell records) but
>> > dependently-typed-list-based implementation, or at the very least
>> > Vinyl (I haven't ever used HList) has the advantage of being dead
>> > simple in both implementation and usage. I mean, with Vinyl, you can
>> > write manual recursion over Rec's like:
>> >
>> > foo :: Rec ... -> Rec ...
>> > foo RNil = ...
>> > foo (r :& rs) = ...
>> >
>> > whenever GHC's typechecker gives up and goes on a strike; and I dare
>> > to say, with commonly used record sizes (have you ever used a record
>> > with more than, let's say, 10 fields?) the speed tradeoff is not
>> > noticeable.
>>
>> While more than 10 fields in a record is uncommon for typical library
>> APIs and simple programs, real world projects can grow much larger
>> records. One example is configuration data for complex programs (like
>> Darcs or even GHC) with many options. It would be so nice if we could use
>> record types for the configuration! Another application could in control
>> system toolkits like EPICS [1], which currently has (actually: generates)
>> C records with potentially hundreds of fields.
>>
>> If lookup is / remains linear we can never efficiently support these
>> kinds of applications and that would be very sad.
>>
>> I think the most reasonable default is O(1) for lookup and O(n) for
>> extension, like in Nikita Volkov's record package. It is quite
>> unfortunate that this package limits the number of fields! If GHC would
>> offer generic support for tuples of arbitrary size (with the same
>> efficiency as today) this limitation could be avoided and all would be
>> well.
>>
>> Cheers
>> Ben
>>
>> [1] http://www.aps.anl.gov/epics/
>> --
>> "Make it so they have to reboot after every typo." ― Scott Adams
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>
--
"Make it so they have to reboot after every typo." ― Scott Adams


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Fwd: Efficient records with arbitrarily many fields [was: Extensible states]

Alexander V Vershilov
Not sure that it will make sense for a cafe level, but here is my
understanding of the current state. For the problem of "anonymous
records", i.e. some datatype that may have different fields and their
types we have following appoaches:

1. vinyl/hlist/etc. i.e. GADT base heterogeneous list. This one have
O(N) random access and may not be a good fit for "anonymous record"
use case

2. records: polymorphic data structures with type-level information
about field names. Here we have a lot of datastructures one per number
of fields multiply on 2 (lazy and strict variant). This one has O(1) random
access.

3. fixed-vector-hetero/"wheel above". array based structures has O(1) access.
I call code above a "wheel" because there were a number of similar
implementations here and there.

I'm not the author or contributor of any libraries above, so I may miss
something, but here is my view: (let's not take a hlist into the scope, because
it should be used in different scenarios).

record provides a good approach + nice syntactic sugar (based on TH or
preprocessor or possibly compiler). The downside here is that we have O(N)
internal structures and exponential number of instances. You could take a look
at records haddock page, use 10% zoom for the best feeling :).

array-based approach have only one structure and 1 instance for any number
of fields, and this is a benefit. But there is a cost as records could be used
even without syntactic sugar (e.g. pattern matching), and with fixed vector it
will be a bit tricker (if possible), for example my approach above as it stands
will not be usable without syntactic sugar similar to the records one. There
is one more problem, library heavily uses `unsafeCoerce` so it should be a
part of the trusted base, of cause this is totally safe as typechecker checks
that, nevertheless it may be a concern for the users.

my wheel could reuse fixed-vector-hetero, as this is basically tagged structure
over fixed vector, I have not reused that because of 2 reasons:
1. I have not found a nice way to update fields in immutable vector (maybe I
just missed that part of API)
2. I don't see a nice way to give user a choice to make fields strict, and in
a wheel it's possible to introduce another typelevel variable that will be used
as a strictness marker, and lens that we build will appreciate that. Btw, here
we may have a solution that is better that "all-or-nothing" one in the records
package.
this solution may well cope with solution for "overloaded records"
that is worked
on.
3. If fixed-vector will not be reused it's possible to convert
structure in O(1).

Anyway records have all required tooling around it, and seems like a best
solution in this (anonymous records with O(1) field access) area at least for
now.


--
Alexander

On 4 July 2015 at 17:19, Ben Franksen <[hidden email]> wrote:

> Thanks, I didn't know of vector-fixed-hetero. Quite interesting.
>
> Anyway, I am not so much interested in getting reasonable efficiency from
> any of the existing libraries right now, as I am in reaching consensus about
> what kind of compiler support would be needed to make any of them practical.
>
> Cheers
> Ben
>
> Alexander V Vershilov wrote:
>> (forgot to reply to cafe list
>> Hi.
>>
>> You can take a look at vector-fixed-hetero [1],
>> that can act as anonymous structure with arbitrary number of fields,
>> convertion to and from
>>
>> datatypes with the same structure and many more features. It's missing
>> field names though
>> and syntactic sugar that 'records' package have. If you like to
>> reinvent a wheel, then
>>
>> you can use following appoach:
>>
>> introduce some typelevel info
>>
>> data a :? (b :: Symbol)
>>
>> data FieldName (t :: Symbol) = FieldName
>>
>> introduce generic structure for records with any number of fiels
>>
>> newtype ARec (m :: [*]) = ARec { unRec :: Array Any }
>> type instance TProxy (ARec m) = m
>> type instance VProxy (ARec m) = ARec
>>
>> rerec :: ARec a -> ARec b
>> rerec = ARec . unRec
>>
>> indexRec :: (KnownNat (FieldIndex name m), FieldType name m ~ a)
>>          => proxy name -> ARec m -> a
>> indexRec name v = unsafeCoerce $
>>   indexArray (unRec v) (fromIntegral (natVal (indexProxy name v)))
>>
>> updateRec :: (KnownNat (Length m), KnownNat (FieldIndex name m),
>> FieldType name m ~ a)
>>           => proxy name -> a -> ARec m -> ARec m
>> updateRec name b v = runST $ do
>>     out <- newArray len undefined
>>     copyArray out 0 (unRec v) 0 len
>>     writeArray out idx (unsafeCoerce b)
>>     ARec <$> unsafeFreezeArray out
>>   where
>>     idx = fromIntegral (natVal (indexProxy name v))
>>     len = fromIntegral (natVal (lengthProxy v))
>>
>> you'll need some typelevel magic for that:
>> type family FieldType (n :: Symbol) m where
>>   FieldType n ((a :? n) ': z) = a
>>   FieldType n (b ': z)        = FieldType n z
>>
>> type family FieldIndex (n::Symbol) m :: Nat where
>>   FieldIndex n ((a :? n) ': z) = 0
>>   FieldIndex n (   b     ': z) = 1 + FieldIndex n z
>>
>> indexProxy :: (KnownNat c, FieldIndex n m ~ c) => proxy1 n -> proxy2 m
>> -> Proxy c
>> indexProxy _ _ = Proxy
>>
>> type family Length m where
>>   Length '[] = 0
>>   Length (x ': xs) = 1 + Length xs
>>
>> lengthProxy :: (KnownNat c, Length n ~ c) => proxy n -> Proxy c
>> lengthProxy _ = Proxy
>>
>> then you can implement lenses:
>>
>> instance (KnownNat (FieldIndex n m), KnownNat (Length m), FieldType n m ~
>> a)
>>          => HasField (n :: Symbol) (ARec m)  a where
>>   getField = indexRec
>>   updateField p = flip (updateRec p)
>>
>>
>> fieldLens' :: (HasField name z a, FieldType name (TProxy z) ~ a)
>>            => FieldName name -> Lens z z a a
>> fieldLens' name = \f m -> fmap (updateField name m)
>>                                (f $ getField name m)
>>
>>
>> type family UpdateType (n :: Symbol) z a b where
>>   UpdateType n ((a :? n) ': z ) a b = (b :? n) ': z
>>   UpdateType n (   z     ': zs) a b =    z     ': UpdateType n zs a b
>>
>> fieldLens :: ( ARec m ~ z, ARec m' ~ z', m' ~ UpdateType name m a b
>>              , FieldType name m  ~ a, FieldType name m' ~ b
>>              , KnownNat (FieldIndex name m), KnownNat (FieldIndex name m')
>>              , KnownNat (Length m), KnownNat (Length m')
>>              ) => FieldName name -> Lens z z' a b
>> fieldLens name = \f m -> fmap (updateField name (rerec m))
>>                               (f $ getField name m)
>>
>> this approach is more or less the same as records package with only one
>> datastructure and almost the same syntactic sugar can be applied, the
>>
>> only missing thing is that pattern matching will be more difficult that
>> with
>>
>> records.
>>
>> At this point it's not possible to write strict fields, but it can be
>> easily extended.
>>
>> If someone is interested in this sort of wheel, I can prepare a package
>> and some
>>
>> docs about and with coercion with other solutions like
>> fixed-vector-hetero and records.
>>
>>
>>
>> [1] https://hackage.haskell.org/package/fixed-vector-hetero
>>
>>
>> On Sat, Jul 4, 2015, 16:08 Ben Franksen <[hidden email]> wrote:
>>>
>>> Marcin Mrotek wrote:
>>> > Okay, perhaps I'm too newbie to understand the big picture, but it
>>> > seems to me you can get either:
>>> >
>>> > a) O(1) access to any, arbitrarily selected (at runtime) field
>>> > b) O(1) append
>>> >
>>> > I guess option a) is better performance-wise, as appending is usually
>>> > done less often than selecting (an O(1) slice is already possible with
>>> > independently typed regular Haskell records) but
>>> > dependently-typed-list-based implementation, or at the very least
>>> > Vinyl (I haven't ever used HList) has the advantage of being dead
>>> > simple in both implementation and usage. I mean, with Vinyl, you can
>>> > write manual recursion over Rec's like:
>>> >
>>> > foo :: Rec ... -> Rec ...
>>> > foo RNil = ...
>>> > foo (r :& rs) = ...
>>> >
>>> > whenever GHC's typechecker gives up and goes on a strike; and I dare
>>> > to say, with commonly used record sizes (have you ever used a record
>>> > with more than, let's say, 10 fields?) the speed tradeoff is not
>>> > noticeable.
>>>
>>> While more than 10 fields in a record is uncommon for typical library
>>> APIs and simple programs, real world projects can grow much larger
>>> records. One example is configuration data for complex programs (like
>>> Darcs or even GHC) with many options. It would be so nice if we could use
>>> record types for the configuration! Another application could in control
>>> system toolkits like EPICS [1], which currently has (actually: generates)
>>> C records with potentially hundreds of fields.
>>>
>>> If lookup is / remains linear we can never efficiently support these
>>> kinds of applications and that would be very sad.
>>>
>>> I think the most reasonable default is O(1) for lookup and O(n) for
>>> extension, like in Nikita Volkov's record package. It is quite
>>> unfortunate that this package limits the number of fields! If GHC would
>>> offer generic support for tuples of arbitrary size (with the same
>>> efficiency as today) this limitation could be avoided and all would be
>>> well.
>>>
>>> Cheers
>>> Ben
>>>
>>> [1] http://www.aps.anl.gov/epics/
>>> --
>>> "Make it so they have to reboot after every typo." ― Scott Adams
>>>
>>>
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> [hidden email]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>>
>>
> --
> "Make it so they have to reboot after every typo." ― Scott Adams
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe



--
Alexander
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
12