- Haskell-Cafe - Haskell.org

Puzzling instance method definitions in Data.Sequence.Internal
by Viktor Dukhovni 02 Mar '21

02 Mar '21

In `containers`, Data.Sequence.Internal defines a Foldable instance for `Seq` with method definitions for `length` and `null` that I'm struggling to understand: https://github.com/haskell/containers/blob/master/containers/src/Data/Seque… #if MIN_VERSION_base(4,8,0) length = length {-# INLINE length #-} null = null {-# INLINE null #-} #endif further down the file there are also explicit top-level definitions for these functions: https://github.com/haskell/containers/blob/master/containers/src/Data/Seque… -- | \( O(1) \). Is this the empty sequence? null :: Seq a -> Bool null (Seq EmptyT) = True null _ = False -- | \( O(1) \). The number of elements in the sequence. length :: Seq a -> Int length (Seq xs) = size xs So the intent seems clear, but I don't understand how the instance method definitions are valid. The imports of Both Prelude and Data.Foldable don't include `length` or `null`: https://github.com/haskell/containers/blob/master/containers/src/Data/Seque… So the RHS definitions should plausibly resolve to the top-level functions, but when I try to define a similar type class instance GHC tells me: ‘method’ is not a (visible) method of class ‘Class’ and in any case I'd expect `length = length` to yield an infinite loop, regardless of any other bindings in the outer scope. How is Data.Sequence.Internal getting away with this??? -- Viktor.

2 2

DatatypeContexts / alternative
by CASANOVA Juan 01 Mar '21

01 Mar '21

Hello again, Haskell Cafe, Here again with another doubt on how am I supposed to. This one should be fairly easier, I believe. In short, I would like to have a functor type that can only be applied to certain type parameters. Why? Well, something like this: module DatatypeContextsExample where import Data.Map import Data.Bifunctor data Foo t = Foo (Map t t) instance Functor Foo where fmap f (Foo m) = Foo (fromList (fmap (bimap f f) (toList m))) This does not compile, because I am using toList and fromList, which require (Ord t). But I cannot really have Foo be a functor in this way without it. The thing is, every time I am going to use it, t is actually going to be Ord. But how do I tell Haskell to have this constraint? DatatypeContexts seems to be the extension that allows this: data Ord t => Foo t = Foo (Map t t) But this has two issues. First, DatatypeContexts is deprecated. Second, more importantly, it still does not type check! It produces the exact same error, saying that Ord t could not be inferred. It should be inferred from the very fact that I am using the type Foo, but GHC does not seem to want to understand this. I could also try with GADTs: data Foo t where Foo :: Ord t => Map t t -> Foo t But this still gives the same error on the fmap definition, stating it cannot use Foo without Ord. But I am pattern-matching against it, shouldn't that be enough to know that (Ord t) is going to hold? I don't understand it. Is there anything simple I am missing? Any other simple way to achieve this? Any fundamental problem with what I am trying to do? Thanks as usual, Juan. The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Is e buidheann carthannais a th' ann an Oilthigh Dhùn Èideann, clàraichte an Alba, àireamh clàraidh SC005336.

5 14

Re: [Haskell-cafe] Not too extensible records?
by Anthony Clayden 01 Mar '21

01 Mar '21

Hi Ignat, as an example of what an extensible records system might look like in Haskell, you could play with Hugs.Trex -- https://www.haskell.org/hugs/pages/hugsman/exts.html#sect7.2 To match a few of its features to your post: > suppose I have two functions: one is a layout algorithm that assigns to nodes some spatial positions, and the second is a topological algorithm that discerns roots and leaves. These two functions are conceptually independent and ... r1 = (label = blah1) r2 = (topology = blah2 | r1) r3 = (v2 = blah3 :: Double | r2) The `( ... | r1)` means extend `r1` with some extra field or fields comma-separated. This is an 'extensible' 'anonymous' records system -- 'anonymous' in that you don't pre-declare your record types via `data`. You can name your record types, either with a `type` decl or with a `newtype` that provides a constructor for known-in-advance types. > may be applied in any order, Yes you can extend an existing record with arbitrary fields, the result is always a 'flat' tuple with the labels-value pairs forming a set: two records are same type providing they have the same set of labels and the same field types at each label, irrespective of how the labels got added. > I would like to make sure their fields are not mixed. > I need to be able to add more and more fields to labels, but in such a way that it is impossible to assign an unsuitable field. There's a so-called 'lacks' constraint you can put on record operations (written with backslash): foo :: r1\topology => Rec r1 -> a -> Rec (edges :: a | r1) is the type of a function that will extend record type `r1` lacking label 'topology' with a field `edges` at type `a`. You can put record types with lacks constraints on instances: instance (r2\v2) => Foo (Rec (label :: String | r2)) (Rec (v2 :: Double, label :: String | r2)) where ... holds for any record that includes label `label` at `String`, and possibly other labels in `r2`, but lacks `v2`. (I'm presuming there's a FunDep on Foo so the second instance parameter is the return type.) > a huge number of `HasThis` and `HasThat` instances That instance head is in effect a `Has` `label` constraint. There's also a shorthand `#label` that generates a function to extract the value at `label` **from any record with a `label`** -- that is, Hugs infers the `Has` constraint for you. > it seems to me that some smart technology is needed to make this manageable. I'm not seeing Trex as 'smart'. It follows conventional relational algebra semantics; was developed ~1996; last release of Hugs was 2006. I'd have thought GHC would come up with something comparable by now. As Olaf's and Henning's replies show, you could fake it with "a lot of boilerplate" and/or some dubious type trickery. AntC

1 0

Desktop GUI in Haskell
by A. Mc. 28 Feb '21

28 Feb '21

Hello, I'm attempting to use GTK+3 to create a Desktop, but I am having a problem installing all of the dependencies. I keep getting the following error: GUI cabal: version >=0.9.0 of pkg-config is required I am using Cygwin on a Windows 10 operating system. What is needed to fix this? Is this the best way to do a desktop GUI in Haskell? Thanks in advance and thank you for your time.

7 6

[ANN] HGeometry-0.12
by Lemmih 28 Feb '21

28 Feb '21

It is our great pleasure to announce version 0.12 of HGeometry! HGeometry is a swiss army knife for computational geometry. Wondering if a point is inside a polygon? HGeometry will tell you. Looking for the shortest path inside a maze? HGeometry will light your way. Planning a museum heist? HGeometry will show you the camera blindspots in O(n log n) time! Check out our website for more: https://hgeometry.org/ HGeometry is open to contributors at all levels of Haskell experience and we have a list of weekend-sized projects. Ask in the Discord server for guidance and/or pair programming. New in 0.12: - Algorithms: - Visibility polygon in O(n log n). - Earclip triangulation in O(n^2) worst case, O(n) expected case. - Single-source shortest path in O(n). - Planar point locator in O(log n). - Point set diameter in O(n log n). - Convex hull of a polygon in O(n). - Diameter of a convex polygon in O(n). - Check if a point lies inside a convex polygon in O(n). - Bug fixes and improved numerical robustness. - Property testing and several methods for generating random polygons. - See changelog.org for an exhaustive list of changes. Future developments: - Bring Haddock documentation coverage up to 100%. Currently, we're in the low eighties. - A holistic approach to demonstrating correctness: - Proven algorithms. - Unit testing for hand-picked corner cases. - Property testing with randomly generated polygons / geometric data. - Exhaustive property testing with real-world datasets (osm). - Benchmarks to show the relative performance of HGeometry's many algorithms. Contributors: - Frank Staals, @noinia - David Himmelstrup, @Lemmih - Hunter DeMeyer, @1ndy Website: https://hgeometry.org GitHub: https://github.com/nionia/hgeometry Hackage: https://hackage.haskell.org/package/hgeometry Discord: https://discord.gg/HQwbD9jWqg

1 0

What is your favourite graph library?
by Ignat Insarov 28 Feb '21

28 Feb '21

Hello! I really like graphs. People seem to like thinking in terms of dots and arrows, and graph theory provides a formalization for this. (Homogeneous binary) relations, finite state automata, networks and categories are sorts of graphs too. But unfortunately it is not possible to represent a graph as an algebraic type. For example, a list is a fixed point of a maybe tuple, and every usual linear container _(an array, a vector, a sequence…)_ is isomorphous to a list, so we have an easy time prototyping and specifying the behaviour of any such thing. With graphs, we have a hard time! The most popular library for graphs in Haskell is `fgl`. Unfortunately, it is really easy to get weird behaviour with it, because folds tear away the limbs from contexts so that your observation of said contexts depends on the order of folding. I have been poking at it, trying to make graphs resemble a comonad… but of course you can have an empty graph, and a comonad cannot be empty. There is also `alga` — it seemed promising, but now it is deprecated for some reason… The usual `containers` also provide something they call a graph, but it does not offer much in terms of instances and algorithms — a graph is merely a type alias to an array. So, is there any cool library that I missed? Or some promising research? Do you know of any packages that use graphs heavily and in interesting ways? Are you curious to see progress in this area?

6 5

Re: [Haskell-cafe] Not too extensible records?
by Olaf Klinke 27 Feb '21

27 Feb '21

> I have a situation that I think is a good case to apply extensible records to. I > have two kinds of entities that are both extensible but in different ways — I > would like to make sure their fields are not mixed. At the same time, I want to > be able to extend the sets of fields across several modules. Is it possible and > is it practical? > My case is that I have a type for graphs that is a bifunctor — in node labels > and edge labels. > So, I need to be able to add more and more fields to labels, but in such a way > that it is impossible to assign an unsuitable field. If your graph is already a bifunctor, why not use a disctinct label or node type in each use case/module? That certainly fits the requirement of not mixing fields. Then you could go the old-fashioned way of type classes, e.g. class HasTopology label where topology :: label -> Topology instance HasTopology Topology where topology = id instance HasTopology label => HasTopology (label,moreInfo) where topology = topology.fst Or for updateable fields, use a Lens Topology. This is a lot of boilerplate, I admit, but you have fine-grained control over what your types have in common. Nested pairs are type- level polymorphic lists and with the right type classes can be used as such, if the list of types is known at compile-time. It is similar to what mtl does with the MonadFoo classes. Olaf

3 3

Not too extensible records?
by Ignat Insarov 27 Feb '21

27 Feb '21

Hello! I have a situation that I think is a good case to apply extensible records to. I have two kinds of entities that are both extensible but in different ways — I would like to make sure their fields are not mixed. At the same time, I want to be able to extend the sets of fields across several modules. Is it possible and is it practical? My case is that I have a type for graphs that is a bifunctor — in node labels and edge labels. I want to gradually decorate these labels with more and more information. For nodes, it may be the number of outgoing edges or the position of the node in space. For edges, it may be whether an edge is directed or not, or whether it was added by some computation, like say transitive closure. So, I need to be able to add more and more fields to labels, but in such a way that it is impossible to assign an unsuitable field. It would be nonsense if a node was said to be undirected or for an edge to be declared a leaf. I would also like not to provide all the labels ahead of time, but rather define whatever labels are needed in the module that defines the corresponding decorating functions. An example for the sort of things I have in mind: class Suitable label type | label → type … data Topology = Root | Internal | Leaf instance Suitable Topology NodeLabels detectTopology ∷ graph someNodeLabels whateverEdgeLabels → graph (someNodeLabels + Topology) whateverEdgeLabels I looked into `extensible` and `vinyl`. * `extensible` does not seem to fit because it defines field labels to be type level strings, making them all interchangeable — there is no way to enforce the distinction between labels suitable for nodes and for edges. * `vinyl` seems to be more flexible and low level, but this also means that it is steeper to learn. The example from the repository uses an enumeration to define a set of labels for a type of records, and this means that the set of labels cannot be extended across modules — this is a problem for me and I am not sure if it can be solved within `vinyl`. What should I do?

1 0

Is there a StateT but with resulting pair swapped?
by Javran Cheng 26 Feb '21

26 Feb '21

Hi cafe, I'm playing with alex recently and noticed that: newtype Alex a = Alex {unAlex :: AlexState -> Either String (AlexState, a)} which is almost StateT AlexState (Except String), and looks like I can make a MonadError instance out of it. Therefore I'm curious if there's any existing package that has newtype StateT' s m a = StateT' (s -> m (s, a)) -- note the swapped pair here so that I can just deriving (MonadError String) via StateT' AlexState (Except String) to implement MonadError. Thanks! -- Javran (Fang) Cheng

2 1

Re: [Haskell-cafe] Problem with stack
by Olaf Klinke 25 Feb '21

25 Feb '21

> Are you building on a networked filesystem? > > Here's a somewhat similar report where switching to a completely local > filesystem has resolved the issue. Speaking of which, is there a specification about what filesystem features stack and its sub-tools expect? I can not build stack projects on a remote cifs share, but on the local filesystem it works fine. The error is Encountered error while migrating Stack database: SQLite3 returned ErrorBusy while attempting to perform step: database is locked Please report this on https://github.com/commercialhaskell/stack/issues I suspect that things like symlinks are expected to work, which samba does not support despite the target drive being ext4. Olaf

4 5