- Haskell-Cafe - Haskell.org

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 22 Oct '16

22 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

Request for help w/ Ex. 10 in *Arrows and Computation*.
by David Banas 22 Oct '16

22 Oct '16

Hi all, I’m stuck in Ex. 10 of *Arrows and Computation*, by Ross Paterson: https://htmlpreview.github.io/?https://github.com/capn-freako/Haskell_Misc/… <https://htmlpreview.github.io/?https://github.com/capn-freako/Haskell_Misc/…> It seems to me that if, in the third step of my proof, I could convert the *left (pure fst)* into *left (first <?>)*, then I could use the **distribution** axiom to convert *pure distr >>> left (first <?>)* into *first (left <?>) >>> pure distr *. At that point, I would have (starting from the left side of my expression): *first (..) >>> first (..)*, and could apply the functor property of *first*, in order to simplify the expression. Thanks, -db

1 0

[ANN] patat - Terminal based presentation tool built with Pandoc
by Jasper Van der Jeugt 20 Oct '16

20 Oct '16

I'm happy to announce `patat` (Presentations Atop The ANSI Terminal), a small tool that allows you to show presentations using only an ANSI terminal. The main features are: - Leverages the great Pandoc library to support many input formats including Literate Haskell. - Supports smart slide splitting. - There is a live reload mode. - Theming support. - Optionally re-wrapping text to terminal width with proper indentation. - Written in Haskell. You can find more information here: https://github.com/jaspervdj/patat/blob/master/README.md Peace, Jasper

15 22

I cannot seem to get the second aio command to work on Create a Game with Haskell hgamer3D.org
by KC 20 Oct '16

20 Oct '16

I'm getting an error 403 permission denied aio http://www.hgamer3d.org/component/CreateProject arriccio is going to download and install the following files: -------------------------------------------------------------- (more license info can be obtained by using the "aio license" cmd) file: http://www.hgamer3d.org/downloads/lua-amd64-windows-1.0.0.tar.gz signing key: https://www.github.com/urs-of-the-backwoods.keys license: MIT License please confirm download with "yes": yes downloading: http://www.hgamer3d.org/downloads/lua-amd64-windows-1.0.0.tar.gz2016/10/20 11:23:56 cannot download urln: http://www.hgamer3d.org/downloads/lua-amd64-windows-1.0.0.tar.gz, http error: 403 -- -- Sent from an expensive device which will be obsolete in a few months! :D Casey

1 0