cocreature 2017-02-22 08:45:21
Hey, warp seems to be killing threads due to timeouts but it so that _after_ the request has finished (see http://lpaste.net/352887 for the output with -xc and stdoutdev logging). Any ideas what could be causing this? it can hardly be the request taking too long it stdout logging already prints the response
ski 2017-02-22 08:45:29
mbrock : now, if you wanted to express `exists a. Show a *> a', then that would become
cocreature 2017-02-22 08:45:31
I'm using servant if that matters
ski 2017-02-22 08:45:51
data Showable = forall a. Show a => Wrap a
ski 2017-02-22 08:45:54
alt.
ski 2017-02-22 08:45:57
data Showable
ski 2017-02-22 08:45:58
where
ski 2017-02-22 08:46:07
Wrap :: Show a => a -> Showable
ski 2017-02-22 08:46:38
mbrock : so it's also straight-forward to encode `*>' in this fashion
ski 2017-02-22 08:47:55
mbrock : btw, note that `Showable' probably isn't that more useful than `String' itself -- you should probably think twice, when about to use an existential, namely think about whether you actually need to extra power (and perhaps headache) of existentials :)
ski 2017-02-22 08:48:04
@where existential-antipattern
lambdabot 2017-02-22 08:48:05
"Haskell Antipattern: Existential Typeclass" by Luke Palmer at
ski 2017-02-22 08:48:09
has some more info on that
mbrock 2017-02-22 08:48:40
ah, yeah
ski 2017-02-22 08:48:43
mbrock : following ? questions ?
Xe 2017-02-22 08:49:00
ski: haskell doesn't have a ternary operator though
ski 2017-02-22 08:49:29
(e.g. note that many things are harder to do with existentials. e.g. making an instance of `Eq' is often impossible)
kadoban 2017-02-22 08:49:32
xD it does, it's just called if then else
ski 2017-02-22 08:49:42
Xe ?
kgadek 2017-02-22 08:50:56
Xe: hmmmmmmmmm `container & lens .~ value` ?
ski 2017-02-22 08:51:06
mbrock : i'll continue with the other encoding now, if you don't object
mbrock 2017-02-22 08:52:22
ski: ok, yes I'm following, go ahead :)
ski 2017-02-22 08:53:37
mbrock : hm, i just recalled i forgot to say earlier that rank-two can be used both (a) when you actually need to use an argument with different polymorphic specializations; and (b) when you want to avoid disclosing through the type signature which particular type you want to use the argument at (information hiding)
ski 2017-02-22 08:54:58
mbrock : so if you see `foo :: (forall a. ..a..) -> ...', it could be either because `foo' needs to use the "callback" with multiple choices of `a', or because it doesn't want to put the actual `a' it picks in the type signature (dropping the `forall'). the latter option is more closely related to existentials (`exists')
ski 2017-02-22 08:55:55
mbrock : one reason for not wanting to put the actual `a' it uses in the type signature could be that it doesn't want the callback to be able to rely on the particular choice
ski 2017-02-22 08:56:56
mbrock : e.g. we could have something like `foo :: (forall a. Foo a -> Bar a) -> ...', where `foo' will provide a value of type `Foo a', perhaps containing a record of available operations on `a', and the caller can't use any other operations on `a' values, apart from these
ski 2017-02-22 08:58:01
mbrock : is an example of the (b) use of rank-two, where i wanted to hide the fact that i used an output (`Writer') monad
ski 2017-02-22 08:58:55
in this case, the argument i supply to the callback will do "logging", but i don't want the callback to be able to mess things up by attempting to insert its own log entries
ski 2017-02-22 08:59:17
mbrock : anyway .. enough about that !
ski 2017-02-22 08:59:43
mbrock : so, continuation-passing style ..
ski 2017-02-22 09:00:32
mbrock : the idea of CPS is that instead of returning a value normally, you instead take an extra argument, the continuation, and instead of returning a value, you call the continuation with the value you wanted to return
mbrock 2017-02-22 09:00:40
yeah
ski 2017-02-22 09:01:08
mbrock : the point of this is that one can then, sometimes, do other things than simply returning through the continuation eventually
ski 2017-02-22 09:01:36
e.g. one could "jump out" of a deeply nested recursion (like an exception would)
ski 2017-02-22 09:02:02
and one can do even stranger things, like a call "returning" more than once
ski 2017-02-22 09:02:25
if you see a type that looks like `(a -> o) -> o', chances are that CPS may be related in some way
ski 2017-02-22 09:02:56
`a' is the type of the "original" return value. `a -> o' is the type of the contiuation which accepts such a value, and produces a value of type `o', the "final result/answer" type
ski 2017-02-22 09:03:10
@src Cont
lambdabot 2017-02-22 09:03:11
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
mbrock 2017-02-22 09:03:46
right
ski 2017-02-22 09:03:51
@type flip all
lambdabot 2017-02-22 09:03:53
Foldable t => t a -> (a -> Bool) -> Bool
ski 2017-02-22 09:03:54
@type cont . flip all
lambdabot 2017-02-22 09:03:57
Foldable t => t a -> Cont Bool a
mbrock 2017-02-22 09:04:21
@type cont
lambdabot 2017-02-22 09:04:23
((a -> r) -> r) -> Cont r a
ski 2017-02-22 09:04:30
it's the data constructor `Cont' above
mbrock 2017-02-22 09:04:36
makes sense
mbrock 2017-02-22 09:04:45
yeah
nitrix 2017-02-22 09:04:58
Is there a O(n) way of mutating an element of a list chosen randomly?
ski 2017-02-22 09:05:09
(except the library got slightly redesigned so that now `Cont o a' is defined as `ContT o Identity a' so the real data constructor is `ContT', hence `cont' rather than `Cont')
ski 2017-02-22 09:05:20
here, we "pretend" that `cont . flip all' will "extract *any* element" of the collection"
kadoban 2017-02-22 09:06:32
nitrix: Check the length, choose a random number in that range, "mutate" that element?
ski 2017-02-22 09:06:32
while, in reality, it'll wrap all the "follwing/surrounding context" (the continuation) of the call as a callback, pass that to `all' for each element of the collection, then use the monoid `True'&`(&&)' to reduce all these `Bool's to a single `Bool' result
ski 2017-02-22 09:07:12
mbrock : anyway, if you treat the "final answer" type `o' abstractly, then you wouldn't be able to do this "strange thing" (adding the extra power of CPS)
ski 2017-02-22 09:07:28
mbrock : i claim that the type `forall o. (a -> o) -> o' is equivalent to just plain `a'
ski 2017-02-22 09:07:53
mbrock : clearly, if `x :: a', then `\k -> k x' has type `forall o. (a -> o) -> o', that's easy
ski 2017-02-22 09:08:47
mbrock : in the other direction, if we have a value of type `forall o. (a -> o) -> o', then since (inside the `forall') it's a function, it must be of the form `\k -> ..k..' (when evaluated enough, unless it's partial, of course)
ski 2017-02-22 09:09:22
mbrock : now, since the type `o' here must be treated opaquely, we know that the only way `..k..' can get hold of a result value of type `o' is by calling `k' on some argument of type `a'
c_wraith 2017-02-22 09:09:33
tangentially, this is why Codensity is better than ContT if your only goal is reinversion of control
ski 2017-02-22 09:10:12
mbrock : it could possibly call `k' on more than one such value, but it must then pick which `o' to return. since the language is non-strict, this means there is some `x :: a' such that the value of type `forall o. (a -> o) -> o' must actually be of the form `\k -> k a'
c_wraith 2017-02-22 09:10:15
the universal quantification prevents lots of continuation tricks.
ski 2017-02-22 09:11:07
mbrock : then, to check that this is an isomorphism, one should also check that going "there and back again" is the same as doing nothing, for both ways of doing that .. but i'll leave that part of the argument "as an exercise" (if you feel like it)
nitrix 2017-02-22 09:11:24
kadoban: Wouldn't this gives me O(2n) ?
kadoban 2017-02-22 09:11:36
O(2n) is the same set as O(n)
nitrix 2017-02-22 09:12:00
I'm not following. The list is traversed twice if I need its length.
ski 2017-02-22 09:12:03
mbrock : this is an *informal* argument (the formal involves something called "parametricity"), but hopefully it should give you some intuition supporting the notion that `forall o. (a -> o) -> o' "ought" to be the same as `a', in terms of the information expressed
kadoban 2017-02-22 09:12:06
If you want, you can use lists annotated with their length though.
ski 2017-02-22 09:12:09
mbrock : does that make sense ?
nitrix 2017-02-22 09:12:19
kadoban: Do Haskell has that :D !?!
kadoban 2017-02-22 09:12:42
nitrix: Not sure if it's in base, I've done it myself ocasionally.
nitrix 2017-02-22 09:12:44
Dependently typed would be even better but I'm keeping my hopes low.
kadoban 2017-02-22 09:13:56
It's not going to change the asymptotic behavior, so I usually wouldn't bother unless it's too slow as-is.
ski 2017-02-22 09:14:04
(as c_wraith said, CPS is related to "inversion of control". it has been used for programs running on, or talking to, web servers, in order to hide the abrupt changes in control between internal computation and waiting for the user to fill in the next form, on the next page)
ski 2017-02-22 09:14:31
mbrock : anyway, this is more or less as much about CPS as i wanted (needed) to explain here ..
mbrock 2017-02-22 09:15:26
ski: yes, I see how `forall o. (a -> o) -> o' must basically be `($ x)' where x :: a
ski 2017-02-22 09:15:38
good
ski 2017-02-22 09:15:56
mbrock : now, we apply this, to get the other encoding (the CPS encoding) of `exists' (and `*>')
mbrock 2017-02-22 09:16:00
it's like the continuation-passing version of `forall a. a'
ski 2017-02-22 09:16:51
mbrock : we start with `exists a. ..a..', which is equivalent to `forall o. ((exists a. ..a..) -> o) -> o', which is equivalent to `forall o. (forall a. ..a.. -> o) -> o'
ski 2017-02-22 09:17:41
mbrock : similarly, starting with `C a *> Foo a', we get `forall o. ((C a *> Foo a) -> o) -> o', which is `forall o. (C a => Foo a -> o) -> o'. having both `exists' and `*>' at the same time is similar
ski 2017-02-22 09:18:11
mbrock : this means that, instead of having
ski 2017-02-22 09:18:31
folkloreQueueOps :: forall a. QueueOps a
ski 2017-02-22 09:18:54
folkloreQueueOps = MkQO (([],[]),enqueue,dequeue)
ski 2017-02-22 09:18:55
where
ski 2017-02-22 09:19:02
enqueue = ...
ski 2017-02-22 09:19:06
dequeue = ...
ski 2017-02-22 09:19:09
we instead do
ski 2017-02-22 09:19:51
withFolkloreQueueOps :: forall a o. (forall q. q -> (a -> q -> q) -> (q -> Maybe (q,a)) -> o) -> o
ski 2017-02-22 09:20:07
withFolkloreQueueOps k = k ([],[]) enqueue dequeue
ski 2017-02-22 09:20:09
where ...
ski 2017-02-22 09:20:34
instead of packing the parts together in the "existential data type", we pass them directly on to the continuation
ski 2017-02-22 09:20:46
and instead of using
ski 2017-02-22 09:20:54
case myQueueOps of
ski 2017-02-22 09:21:07
(emptyQ,enQ,deQ) -> ..emptyQ..enQ..deQ..
ski 2017-02-22 09:21:10
we use
ski 2017-02-22 09:21:23
withMyQueueOps (\(emptyQ,enQ,deQ) ->
ski 2017-02-22 09:21:28
..emptyQ..enQ..deQ..)
mbrock 2017-02-22 09:21:37
oh, this seems quite clever
mbrock 2017-02-22 09:22:48
so this way we don't need to make a data type
ski 2017-02-22 09:22:48
so instead of the syntactic noise of having to say `Wrap' in `[Wrap "False",Wrap True]' when wanting to express `[exists a. Show a *> a]', we instead have the noise of taking a continuation in `[\k -> k "False",\k -> True]' (or with `($ ...)', if you prefer here)
ski 2017-02-22 09:23:11
similarly, when using, you have to provide a lambda (or a named function), instead of a `case'
ski 2017-02-22 09:23:19
so the noise isn't that much different
ski 2017-02-22 09:23:46
the data type encoding would typically be used when you want/need to store your existentially typed values in data structures
platz 2017-02-22 09:24:10
i think i may have to make a quasiquoter library for hex literals
ski 2017-02-22 09:24:20
while the CPS encoding would typically be used when you simply want to transmit your existentially typed value to the caller, who immediately then unwraps it and uses it
aweinstock 2017-02-22 09:24:38
are "lenses over the values in an STRef" a concept that makes sense?
ski 2017-02-22 09:24:41
also the CPS encoding doesn't force you to invent a new data type, so it's more lightweight in that sense
nitrix 2017-02-22 09:24:45
kadoban: Turns out Data.Sequence is perfect for this.
ski 2017-02-22 09:24:47
mbrock : *nod*
platz 2017-02-22 09:25:00
it' very easy in e.g. python to write a literal such as 0xFEFE
nitrix 2017-02-22 09:25:00
kadoban: O(1) length and O(log(min(i,n-i))) adjust.
aweinstock 2017-02-22 09:25:06
(if they are, I don't see them defined inside lens (using 'grep -r STRef' and 'grep -r IORef' in the repository)
aweinstock 2017-02-22 09:25:09
)
ski 2017-02-22 09:25:47
mbrock : .. it would be nice if there would be actual syntactic support of `exists' (and `*>') .. but now you know how you can encode it in two different ways
kadoban 2017-02-22 09:26:04
nitrix: Seems possible.
mbrock 2017-02-22 09:26:54
ski: yeah, thanks a lot for the introduction!
ski 2017-02-22 09:27:04
mbrock : btw, consider again `data Showable = forall a. Show a => Wrap a'. in the dictionary-passing translation of constraints, this becomes `data Showable = forall a. Wrap (ShowDict a) a' .. this explains why you can't use `newtype' with "existential data types". .. if you don't have any constraints, you could argue for it being possible, though
ski 2017-02-22 09:28:23
mbrock : however, one could consider implementations which actually pass at run-time info around for `forall' and `exists' (perhaps not insisting on boxing and so e.g. `length' has to know the size, and maybe other layout of values of type `a' at run-time) .. and insisting on `newtype' existentials would preclude that
ski 2017-02-22 09:29:11
mbrock : i think that's what i wanted to cover here. there's other interesting things one could consider, e.g. relation to OO, and relation to recursive types. perhaps another time, if you're interested
prohobo 2017-02-22 09:30:48
STOP THAT
