- Haskell-Cafe - Haskell.org

Proof of concept of explanations for instance resolution
by Michael Sloan 27 Oct '16

27 Oct '16

When typeclass machinery gets complicated, it can be hard to figure interpret the meaning behind GHC's messages. In particular "Could not deduce ..." messages often reference constraints that are deep in a tree of resolving typeclasses. I think it would be great if GHC provided additional information for this circumstance. In a way what we need is a "stack trace" of what GHC was thinking about when yielding these type errors. A couple years ago, I wrote an extremely hacky approach to yielding this information through TH. It is quite imperfect, and only works with GHC 7.8. I've realized that it's highly unlikely that this project will reach the level of polish for it to be very usable in practice: https://github.com/mgsloan/explain-instance However, rather than allow that work to be wasted, I'd like to bring people's attention to the problem in general, and how we might solve it in GHC. Along with providing more information in type errors, this could also look like having a ":explain" command in ghci. Lets take Text.Printf as an example. The expression (printf "%d %d" (1 :: Int) (2 :: A) :: String) has quite a bit of machinery behind it: printf :: (PrintfType r) => String -> r class PrintfType t instance (IsChar c) => PrintfType [c] instance (a ~ ()) => PrintfType (IO a) instance (PrintfArg a, PrintfType r) => PrintfType (a -> r) class PrintfArg a where instance PrintfArg Int where With explain-instance, all we have to do is create a module with the following in it: import ExplainInstance import Text.Printf $(explainInstance [t| PrintfType (Int -> Int -> String) |]) Then, upon running the generated main function, we get the following explanation: instance (PrintfArg a, PrintfType r) => PrintfType (a -> r) with a ~ Int r ~ (Int -> [Char]) instance PrintfArg Int instance (PrintfArg a, PrintfType r) => PrintfType (a -> r) with a ~ Int r ~ [Char] instance PrintfArg Int instance IsChar c => PrintfType ([c]) with c ~ Char instance IsChar Char This is the recursive tree of instance instantiation! It shows the instance head, the particular types that it has been instantiated at in a made up "with" clause. Most importantly, it shows how the instance's constraints are also satisfied, giving a tree for an explanation. The implementation of this is irrelevant, but for the curious: it involves recursively reifying all of the typeclasses, and then generating a whole new set of typeclasses. These modified versions have the same heads (renamed) as the original typeclasses, but just have one method, which yields a description of the the types it has been instantiated with, via Typeable. Well that's quite convenient! I think it can really aid in understanding typeclass machinery to be able to get this variety of trace through what GHC is thinking when satisfying a constraint. However, this is just half the problem - what about type errors? I played around with a solution to this via UndecidableInstances, where it would create a base-case instance that represents the error case. Lets say I wanted to use (printf :: String -> A -> Int -> Maybe String) where A is a type that is not an instance of PrintfArg. Another issue with this is that the result type (Maybe String) is not allowed by PrintfType. The output of $(explainInstanceError [t| PrintfType (A -> Int -> Maybe String) |]) is instance (PrintfArg a, PrintfType r) => PrintfType (a -> r) with a ~ A r ~ (Int -> Maybe [Char]) ERROR instance PrintfArg a with a ~ A instance (PrintfArg a, PrintfType r) => PrintfType (a -> r) with a ~ Int r ~ Maybe [Char] instance PrintfArg Int ERROR instance PrintfType t with t ~ Maybe [Char] This explains exactly where the problem is coming from in the typeclass machinery. If you're just looking at the type of printf, and see a `PrintfType` constraint, it can be a total mystery as to why GHC is complaining about some class we may or may not know about: No instance for (PrintfArg A) arising from a use of ‘printf’ Thanks for reading! I hope we can address this UI concern in the future. I hope I've contributed something by demonstrating the possibility! -Michael

2 1

Suggestion for error message improvement
by Zachary Kessin 26 Oct '16

26 Oct '16

When I compiled some code this morning I got an error that said that I should edit my cabal file, but I notice that one thing is missing, the path to the cabal file. Having that in the error message would make fixing it a bit easier and faster in that emacs could take me right to the correct cabal file and that I would know for sure which one it was using. I tried filing this as a bug on the stack github repo but they said it is a ghc issue. [1 of 1] Compiling Main ( tests/test.hs, .stack-work/dist/x86_64-linux/Cabal-1.24.0.0/build/test/test-tmp/Main.o ) /home/zkessin/Documents/*****/tests/test.hs:17:1: error: Failed to load interface for ‘Control.Lens’ It is a member of the hidden package ‘lens-4.14’. Perhaps you need to add ‘lens’ to the build-depends in your .cabal file. Use -v to see a list of the files searched for. Progress: 1/2 -- While building package ***********-0.1.0.0 using: /home/zkessin/.stack/setup-exe-cache/x86_64-linux/setup-Simple-Cabal-1.24.0.0-ghc-8.0.1 --builddir=.stack-work/dist/x86_64-linux/Cabal-1.24.0.0 build lib:********** test:test --ghc-options " -ddump-hi -ddump-to-file" Process exited with code: ExitFailure 1 -- Zach Kessin SquareTarget <http://squaretarget.rocks?utm_source=email-sig> Twitter: @zkessin <https://twitter.com/zkessin> Skype: zachkessin

2 1

[ANN] unicode-transforms-0.2.0 pure Haskell unicode normalization
by Harendra Kumar 26 Oct '16

26 Oct '16

Hi, I released unicode-transforms sometime back as bindings to a C library (utf8proc). Since then I have rewritten it completely in Haskell. Haskell data structures are automatically generated from unicode database, so it can be kept up-to-date with the standard unlike the C implementation which was stuck at unicode 5. The implementation comes with a test suite providing 100% code coverage. After a number of algorithmic and implementation efficiency optimizations, I was able to get several times better decompose performance compared to the C implementation. I have not yet got a chance to fully optimize the compose operations but they are still as fast as utf8proc. I would like to thank Antonio Nikishaev for the unicode character database parsing code which I borrowed from the prose library. https://github.com/harendra-kumar/unicode-transforms https://hackage.haskell.org/package/unicode-transforms -harendra

2 2

A composable, local graph representation as an open discussion
by David Rogers 25 Oct '16

25 Oct '16

Haskell-Cafe: I have been working on the following idea, and would appreciate any comments on the novelty or usefulness in your own applications. A scan of the usual Haskell documents turns up lots of clever data structures, but nothing particularly enlightening for graphs. Here is my attempt: Graphs are difficult to represent in functional languages because they express arbitrary undirected connectivity between nodes, whereas functional code naturally expresses directed trees. Most functional algorithms for graphs use an edge-list with global labels. Although effective, this method loses compositionality and does not exploit the type system for enforcing graph invariants such as consistency of the edge list. This note presents a functional method for constructing a local representation for undirected graphs functionally as compositions of other graphs. The resulting data structure does not use unique node labels, but rather allows edge traversal from any node to its neighbor through a lookup function. Graph traversal then emerges as a discussion among static nodes. I have found this method useful for assembling sets of molecules in chemical simulations. It's also an interesting model for framing philosophical questions about the measurement problem in quantum physics. As a disclaimer, although it is useful for constructing graphs, it is not obvious how common operations like graph copying or node deletion could be performed. This note does not discuss how to implement any graph algorithms. > import qualified Prelude > import Prelude hiding ((.)) > import Data.Semigroup(Semigroup,(<>)) > import Data.Tuple(swap) First, I change the meaning of "." to be element access. I think this is a cleaner way to work with record data, and suggest that there should be a special way to use this syntax without making accessor names into global variables. > infixl 9 . > a . b = b a -- switch to member access Every subgraph has open ends, which we just number sequentially from zero. The lookup function provides the subgraph's window to the outside world. Its inputs reference outgoing connections. A subgraph, built as a composite of two subgraphs, will have the job of providing the correct lookup environment to both children. > type Conn = Int > newtype Lookup l = Lookup ( Conn -> (l, Lookup l) ) The tricky part is making the connections between the internal and external worlds. For the internal nodes to be complete, they must have access to complete external nodes. The problem is reversed for the external nodes. A naive idea is to represent a graph using a reader monad parameterized over label and result types (l,r). -- newtype Grph l r = Reader (Int -> (l, Lookup)) r Unfortunately, this breaks down because the outside world also needs to be able to `look inside' the subgraph. The above approach runs into trouble when constructing the lookup function specific to each child. That lookup function needs the outside world, and the outside world can't be completed without the ability to look inside! We capitulate to this symmetry between the graph and its environment by using a representation of a subgraph that provides both a top-down mechanism for using the graph as well as a bottom-up representation of the subgraph to the outside world. > data Grph l r = Grph { runGrph :: Lookup l -> r, > self :: Conn -> Lookup l -> (l, Lookup l), > nopen :: Int > } The default action of `running' a graph is to run a local action on each node. That local function has access to the complete graph topology via the lookup function. Since we expect this to be a fold, the result type will probably be a monoid, or at least a semigroup. Any sub-graph can be run by specifying what to do with incomplete connections. At the top-level, there should not be `open' connections. >--run g = (g.runGrph) $ Lookup (\ _ -> error "Tried to go out of top-level.") > run g = (g.runGrph) $ u > where u = Lookup $ \ _ -> ("end", u) Individual nodes are themselves subgraphs. Nodes must specify how many external connections can be made, as well as an arbitrary label and an action. > node :: Int -> l -> ((l, Lookup l) -> r) -> Grph l r > node n l run = Grph (\e -> run (l, e)) (\_ e -> (l, e)) n Arbitrary graphs are constructed by joining two subgraphs. The key here is the construction of separate lookup environments for the each subgraph. The left subgraph can be connected to the first few openings in the environment or to the right subgraph. The right subgraph can connect to the last few openings of the environment, or to the left subgraph. Each time an edge is traversed, a series of "env" calls are made -- sweeping upward until an internal connection happens. Then a downward sweep of "self" calls are made. This takes at best O(log|nodes|) operations. Connections are specified by (Conn,Conn) pairs, so we need the ability to lookup from the permutation or else to return the re-numbering after subtracting connections used by the permutation. > type Permut = [(Conn, Conn)] > find_fst :: Conn -> Permut -> Either Conn Conn > find_fst = find1 0 where > find1 n a ((a',b):tl) | a == a' = Left b -- internal > find1 n a ((a',_):tl) | a' < a = find1 (n+1) a tl > find1 n a (_:tl) = find1 n a tl > find1 n a [] = Right (a-n) -- external > find_snd b p = find_fst b (map swap p) >-- append 2 subgraphs > append :: (Semigroup r) => Permut -> Grph l r -> Grph l r -> Grph l r > append p x y = Grph { runGrph = \(Lookup env) -> > (x.runGrph) (e1 env) > <> (y.runGrph) (e2 env), > self = down, > nopen = (x.nopen) + (y.nopen) - 2*(length p) > } > where > down n (Lookup env) | n < ystart = (x.self) n (e1 env) > down n (Lookup env) = (y.self) (n-ystart) (e2 env) > e1 env = Lookup $ \n -> case find_fst n p of > Right m -> env m > Left m -> (y.self) m (e2 env) > e2 env = Lookup $ \n -> case find_snd n p of > Right m -> env (m+ystart) > Left m -> (x.self) m (e1 env) > ystart = (x.nopen) - length p -- start of b's env. refs This is a helper function for defining linear graphs. > instance Semigroup r => Semigroup (Grph l r) where > (<>) = append [(1,0)] A simple action is just to show the node labels and the labels of each immediate neighbor. > show_node (l, Lookup env) = " " ++ show l > show_env (l, Lookup env) = show l > ++ foldl (++) (":") (map (\u -> show_node(env u)) [0, 1]) > ++ "\n" The following example graphs are a list of 4 single nodes, two incomplete 2-member chains, and a complete 4-member cycle. The key feature here is that that the graphs are all composable. > c6 = [ node 2 ("C"++show n) show_env | n <- [1..4] ] > str = c6!!0 <> c6!!1 > str' = c6!!2 <> c6!!3 > cyc = append [(1,0), (0,1)] str str' -- Tying the knot. > main = putStrLn $ run cyc The connection to the measurement problem in quantum physics comes out because the final output of running any graph is deterministic, but can depend nontrivially on the graph's environment. Like links in the graph, physical systems communicate through their mutual interactions, and from those determine a new state a short time later. In a closed universe, the outcome is deterministic, while for any an open system (subgraph), the outcome is probabilistic. The analogy suggests that understanding how probabilities emerge in the measurement problem requires a two-way communication channel between the system and its environment. ~ David M. Rogers

4 4

What did you/do you find hard/dislike about Opaleye?
by Tom Ellis 25 Oct '16

25 Oct '16

I'm planning to update and refresh Opaleye's documentation and add some new functionality for common use cases. To help with this I'd like to request input from anyone who has ever tried the library. Specifically, what do you (or did you) find hard about using Opaleye and what did you dislike about it? If you tried it and gave up, what was the major sticking point? I'm already aware that many people dislike the boilerplate involved in defining your tables and types, and the polymorphic products are particularly uncomfortable for some. You don't need to mention these issues unless you particularly want to! Feel free to contact me privately or reply directly. Many thanks. Tom

2 3

Left Associativity and Precendence
by Steven Leiva 23 Oct '16

23 Oct '16

Hi folks, Haskell beginner here. I ran across the expression below (from the Haskell Programming From First Principles <http://www.haskellbook.com> book), and I was having a hard time putting parenthesis around the expression in order to make the order of application more explicit. Here is the expression in question: *take 5 . filter odd . enumFrom $ 3* I realize that part of the hang-up that I was having was that I focused solely on the fact that function application is left-associative, and not on the fact that specific functions / operators can have a declared precedence. Once I realized that the $ operator has a declared precedence of 0, the expression took on the following form: *(take 5 . filter odd . enumFrom) $ (3)* Now, everything to the left of the $ operator is simply function application (whitespace) and the function composition operator. I made the same mistake again of ignoring the fact that particular functions / operators can have a declared precedence. Realizing that mistake, and that the function composition has a declared precedence of 9, then the expression took on this form: *((take 5) . (filter odd) . (enumFrom)) $ (3)* So, the general rule that I took away from this is that, when trying to imagine how an expression reduces to normal form, function application does indeed proceed from left to right, but we have to take into account the declared precedence of particular functions / operators. Is my thinking correct here? Are there any particular holes in this logic? I still don't think I'd be able to figure out "where the parenthesis go" if I was given a new expression with functions / operators with 3 or 4 different declared precedences. For a beginner, is that a huge problem, or is knowledge of the concept enough?

3 2

Off-the-shelf Configurable BFT
by Jonn Mostovoy 23 Oct '16

23 Oct '16

Dear all, we're implementing a variant of cryptocurrency with deleged forgers. It is distributed in building ledger and decentralized in nodes participating jn forming transactions. For this we would need to have a BFT algorithm to govern the views on the network and deal with partitions. Implementation has to be industrial-strength and used in production. We're willing to contribute actively to such implementation development. We're looking at HoneyBadgerBFT as an ideal candidate, but it's not implemented in Haskell. The only BFT algorithm implementation we found is a toy RaftBFT implementation. If you have an opensource BFT implementation, or proprietary BFT implementation you would like to trade, please report those implementations here. If you need more details on our use case, don't hesitate to ask. Everything we do is open source and me or my colleagues will gladly answer any questions you might have. Sincerely yours, Jonn Mostovoy, Cardano SL Project Managet at IOHK | Serokell https://serokell.io https://iohk.io

3 2

Wiki account Request
by Siddharth Bhat 23 Oct '16

23 Oct '16

Hey, I'd like a wiki account to edit the Template Haskell pages (the links to the user guide are broken) preferred username: bollu Also, I think it's a little ridiculous to have this be a closed thing (I can't simply register to the wiki). Shouldn't the barrier to entry be _lowered_? Thanks, Siddharth -- Sending this from my phone, please excuse any typos!

5 4

Obtaining location of subexpressions from Template Haskell
by Alejandro Serrano Mena 23 Oct '16

23 Oct '16

Dear Haskell-café, I am trying to write a small TH module which manipulates Haskell code. Basically, I have a function `transform :: Exp -> Q Exp` which I call this way: > g = $(transform [| map (+1) [1,2,3] |]) Since this is a source-to-source transformation, I would like to generate also {-# LINE ... #-} pragmas to point any error back to their original location. My question is: is there any way to obtain the location of sub-expressions inside a `Exp` or `Q Exp`? Thanks in advance, Alejandro

2 1

Munich Haskell Meeting, 2016-10-25 @ 19:30
by Christian Neukirchen 23 Oct '16

23 Oct '16

Dear all, Next week, our monthly Munich Haskell Meeting will take place again on Tuesday, October 25 at **Augustiner-Gaststätte Rumpler (Baumstraße 21)** at 19h30. Please note the new location! For details see here: http://muenchen.haskell.bayern/dates.html If you plan to join, please add yourself quickly to this dudle so we can reserve enough seats! It is OK to add yourself to the dudle anonymously or pseudonymously. https://dudle.inf.tu-dresden.de/haskell-munich-oct-2016/ Everybody is welcome! cu, -- Christian Neukirchen <chneukirchen(a)gmail.com> http://chneukirchen.org

1 0