- Haskell-Cafe - Haskell.org

FFT, via homogeneous functions?
by David Banas 07 Nov '16

07 Nov '16

Hi all, I’m trying to implement the fast Fourier transform (FFT), using the homogeneous functions described in Sec. 4.2 of *Arrows and Computation* by Ross Paterson: -- FFT implementation -- Note my reversal of Ross' even/odd convention, below. -- I did this, to remain consistent with the explanation, above, which came from a pre-existing work. fft :: RealFloat b => Hom (Complex b) (Complex b) fft = id :&: proc (e, o) -> do e' <- fft -< e o' <- fft >>> twiddle -< o unriffle -< f (e', o') where f (x, y) = (x + y, x - y) twiddle :: RealFloat b => Hom (Complex b) (Complex b) twiddle = id :&: twiddle' 1 twiddle' :: RealFloat b => Int -> Hom (Pair (Complex b)) (Pair (Complex b)) twiddle' n = (id *** (* phi)) :&: (((twiddle' n') *** ((twiddle' n') >>> (arr ((* phi) `prod` (* phi))))) >>> unriffle) where phi = cis (-pi / (fromIntegral (2 ^ n))) n' = n + 1 I’m getting this output, which means that, while my *twiddle* function is working for all tree depths tested, my *fft* function fails for tree depths greater than 3: Tree depth: 0 Testing twiddles...True Testing FFT...True Tree depth: 1 Testing twiddles...True Testing FFT...True Tree depth: 2 Testing twiddles...True Testing FFT...True Tree depth: 3 Testing twiddles...True Testing FFT...True Tree depth: 4 Testing twiddles...True Testing FFT...False Tree depth: 5 Testing twiddles...True Testing FFT...False And I’m wondering if anyone sees the flaw in my code. More here: https://htmlpreview.github.io/?https://github.com/capn-freako/Haskell_Misc/… <https://htmlpreview.github.io/?https://github.com/capn-freako/Haskell_Misc/…> Thanks! -db

1 0

Guidance on symbol error
by Christopher Howard 07 Nov '16

07 Nov '16

Hi list. I'm trying to build gruff on Debian Jessie with GHC 7.6.3. I'm building gruff-0.3.3 because gruff-0.3.4 dependencies seem to be too new for Jessie. I was able to build all the dependencies of gruff-0.3.3 (after installing a ton of -dev packages). But when cabal tries to build the gruff package itself, I get this error: /usr/bin/ld: dist/build/gruff/gruff-tmp/src/compute.o: undefined reference to symbol '_ZdaPv@@GLIBCXX_3.4' //usr/lib/x86_64-linux-gnu/libstdc++.so.6: error adding symbols: DSO missing from command line It's been quite a while since I did any C++ programming... could somebody clarify for me what this means? Thank you. -- https://qlfiles.net My PGP public key ID is 0x340EA95A (pgp.mit.edu)

2 1

ResourceT "unmasked" during allocation?
by Viktor Dukhovni 07 Nov '16

07 Nov '16

I am looking at using ResourceT to manage the acquisiition and deallocation of network sockets. In comparing resourceT's `allocate` with `bracket` I was somewhat perplexed to find that `allocate` in Control.Monad.Trans.Resource seems to not mask exceptions during allocation (see "No mask" comment I inserted): allocateRIO :: IO a -> (a -> IO ()) -> ResourceT IO (ReleaseKey, a) allocateRIO acquire rel = ResourceT $ \istate -> liftIO $ E.mask $ \restore -> do a <- restore acquire -- ^^^ No mask ^^^ key <- register' istate $ rel a return (key, a) allocate :: MonadResource m => IO a -- ^ allocate -> (a -> IO ()) -- ^ free resource -> m (ReleaseKey, a) allocate a = liftResourceT . allocateRIO a By contrast in Exception.Base we see that `bracket` masks the initialization action: bracket before after thing = mask $ \restore -> do a <- before -- ^^^ masked! ^^^ r <- restore (thing a) `onException` after a _ <- after a return r This seems to suggest that ResourceT is more exposes to resource leaks via asynchronous exceptions. Say if a file descriptor is a allocated, but an exception interrupts "allocate" before it can register the resource. Perhaps I am missing something, or there are good reasons for the difference in approach. Can anyone shed some light on the reason why ResourceT differs (seemingly) from bracket in this regard. -- Viktor.

2 1

Re: [Haskell-cafe] programming style...and type classes...
by Olaf Klinke 06 Nov '16

06 Nov '16

While we have stated in this thread what typeclasses should _not_ be used for, we probably do not have carved out yet what `proper' use is. Please help me here. There are some typeclasses, e.g. Eq, Ord, Num, Monoid, Functor, Monad and Category, that arise from category theory and algebra, so these may be regarded as "good" typeclasses even though a type can have several sensible instances. In that case, newtypes may express this. (Data.Monoid is full of such newtypes.) In defense of Ord, there are in general many ways to totally order a set (read "set" as "total elements of a type"), and none of these ways can be preferred a priori. I would not say this is an inherently bad property of Ord. Similarly, there are many ways to put a monoid or ring structure on a set. Sometimes a type class can be avoided. For example, there is Data.Foldable.toList. Hence, instead of writing a Foldable instance for your type and use a function from the Data.Foldable module, you could instead write your own toList conversion function and then fold that list. (Does anyone know a function involving Foldable that can not be reduced to 'toList' followed by some list operations? Is [] the "free instance" of Fodable?) However, this reduction may be much more inefficient than using the Foldable instance directly. As a contrived example of what I mean by "free instance", consider the following class that abstracts traversal over a sequence of unknown length. class ListLike l where patternmatch :: l a -> Maybe (a,l a) You can write ListLike instances for [], Vector, Sequence and Set, but only [a] is the solution to the type equation x = Maybe (a,x). Then there are multi-parameter type classes. This has been described as metaphorical to a type-level Prolog language [1], since ultimately multi-parameter type classes (without methods) are relations between types. Another debatable use case: You define many record types, each of which has a sort key component: data A = A {foo :: Foo, bar :: Bar, keyA :: Int} data B = B {baz :: Baz, keyB :: Int} data C = C {... , keyC :: Int} It might be convenient to define a typeclass class HasSortKey a where key :: a -> Int and endow the types A, B and C with the obvious instances. But one could also avoid the class by making a parametric type: data Keyed a = Keyed {payload :: a, key :: Int} and then let data A = A {foo :: Foo, bar :: Bar} and so forth. Which version would you say is `proper' use? -- Olaf [1] https://www.reddit.com/r/haskell/comments/ck459/typed_typelevel_programming…

3 2

typeclass constraints?
by Gregory Guthrie 05 Nov '16

05 Nov '16

I want to define a bunch of tests in a simple demo program, where each test is locally defined, but all can be printed in one standard place. For example, each test result has a description::String, and a value, which can vary across tests. t1 = ("Sqrt(4)", sqrt(4.0)) ... t2 = ("sumList:", sum [1,2,3,4]) ... t3 = ("Description", value) ... So each test is of type: (String, value), for various value types all of which (only) have to be members of the Show class. Then for the summary of the tests, a loop: test (msg, val) = do print $ msg ++ " :: " ++ show val tests ts = mapM test ts ... Do tests [t1, t2, t3] This compiles, and assigns these types: test :: Show a => ([Char], a) -> IO () tests :: (Traversable t, Show a) => t ([Char], a) -> IO (t ()) Which works only as long as all tests have the same type for the second argument. I assume that it is somehow specializing the type to the actual encountered type of the arguments used, even though they are all show'able. So that they can vary on the actual types of the second argument, I tried something like this (pseudo code): type ATest = (Show a) => (String, a) since that wouldn't work, I tried: {-# LANGUAGE RankNTypes #-} type ATest = forall a. (Show a) => (String, a) Which compiles, but still fails on any variation in the value argument. Further, I want to abstract the type of tests from the loop which prints them, but I cannot then use it to convert from: test :: Show a => ([Char], a) -> IO () to test :: ATest -> IO () The basic idea was to define and use a polymorphic type for the tests in the definition of the testing loop. So perhaps a data structure instead; data (Show a) => ATest = Test (String, a) but that also fails, although it does give the right idea; all tests have a common structure, with a second value in the Show typeclass. I realize that generally one is recommended not to put constraints on the data type, but on the functions which use it - but here since I want a collection of tests it seems like I need a polymorphic list with consistent types. What is the right approach for this? Am I just getting the syntax wrong?

3 3

[ANN] github-0.15
by Oleg Grenrus 04 Nov '16

04 Nov '16

Hi, today I finally released a new version of `github` package [1], providing bindings to the most of GitHub API. [2] The most notable feature, it’s now compatible with GHC-8.0.1. As GitHub doesn’t provide (or I’m not aware of) machine readable specification of their API, the feature completeness and correctness depends on the users of the package. So, please try it out, find out what’s incorrect and missing, and ideally submit a PR. The plan for the next version is to merge in definitions from github-types [3], and then split types from `github` package back into `github-types`, so others can reuse the definitions without the rest of the packages, e.g. for servant-github [4] As you can see, we are still experimenting with “how to write bindings to rest APIs”, if you have some comments, please raise an issue. Cheers, Oleg Grenrus - [1]: http://hackage.haskell.org/package/github <http://hackage.haskell.org/package/github> - [2]: https://developer.github.com/v3/ <https://developer.github.com/v3/> - [3]: http://hackage.haskell.org/package/github-types <http://hackage.haskell.org/package/github-types> - [4]: http://hackage.haskell.org/package/servant-github <http://hackage.haskell.org/package/servant-github>

2 1

[ANN] Haskell ITA meetup in Bologna, Italy (2016-11-19)
by Francesco Ariis 04 Nov '16

04 Nov '16

Hello -cafe, the Italian Haskell Community (http://haskell-ita.it/) is happy to announce its autumn Haskell meetup! The event is going to be hosted in Bologna, on November 19th. The meeting will be in italian; we are going to form small groups/projects, to see Haskell in action and to share knowledge and opinions on functional programming. Everyone, experienced or not, is welcome, just make sure to have a laptop and a working Haskell environment! For a more detailed description of the event and to register, check: https://www.metooo.io/e/haskell-day-bologna (further information in italian follows) ----- - Dove: Bologna, Giardini Margherita, nella struttura "La Gabbia del Leone" (http://leserre.kilowatt.bo.it/gabbia-del-leone/) presso "Le Serre dei Giardini". - Quando: Sabato 19 Novembre, dalle 10:00 alle 18:00. - Chi: chiunque sia interessato alla programmazione funzionale, indipendentemente dal suo livello di esperienza. - Cosa faremo: lavoreremo in gruppi (2-6 persone circa) su diversi progetti. Ogni persona può scegliere il progetto che vuole, saranno date delle indicazioni sul livelo di conoscienza richiesto per contribuire. Lo scopo è provare a utilizzare Haskell per un progetto concreto, "toccare con mano" il modo che hanno altri di lavorare e di condividere le esperienze nelle numerose pause di gruppo. Lo scopo è puramente didattico, quindi nessuna ansia. - Cosa portare: un computer portatile e un ambiente Haskell configurato. - Come arrivare: dalla Stazione Centrale dei Treni di Bologna, prendere l'autobus 33 (frequenza 15 minuti) e scendere alla fermata "Giardini Margherita" e/o "Porta Santo Stefano" (circa 20 minuti di viaggio). Entrare nei Giardini Margherita, dall'ingresso di Via Castiglione 136 o Via Polischi 9, e recarsi presso "Le Serre dei Giardini", alla struttura "La Gabbia del Leone" (http://leserre.kilowatt.bo.it/gabbia-del-leone/) - Grazie a chi: all'associazione [Kilowatt](http://kilowatt.bo.it/about) che ha messo a disposizione gratuitamente la sala. - Per iscriversi: https://www.metooo.io/e/haskell-day-bologna

1 0

memory leak when using "forever"
by Zoran Bosnjak 04 Nov '16

04 Nov '16

Hello all, can you please explain why does this simple program leak memory. But, if I replace loop2 with loop1 (that is: without using "forever"), then it does not leak. Is this a problem in "forever" implementation or am I misusing this function? In the sources of base: http://hackage.haskell.org/package/base-4.9.0.0/docs/src/Control.Monad.html… ... there is some mention of memory leak prevention, but it looks like something is not right in this case. import Control.Concurrent import Control.Monad import Control.Monad.Trans import Control.Monad.Trans.Reader import Control.Monad.Trans.State main :: IO () main = do --let loop1 = (liftIO $ threadDelay 1) >> loop1 let loop2 = forever (liftIO $ threadDelay 1) _ <- runStateT (runReaderT loop2 'a') 'b' return () regards, Zoran

2 3

simple diagrams about GHC development flow
by Takenobu Tani 04 Nov '16

04 Nov '16

Hi cafe, For myself and new contributors, I drew overview diagrams about GHC development flow. GHC development flow http://takenobu-hs.github.io/downloads/ghc_development_flow.pdf https://github.com/takenobu-hs/ghc-development-flow Let's enjoy :) Regards, Takenobu

1 0

Re: [Haskell-cafe] programming style...and type classes...
by Olaf Klinke 03 Nov '16

03 Nov '16

Mark, Haskell typeclasses are a wonderful thing to have. I dare say that typeclasses are what makes haskell code modular and re-usable, because you can develop an algorithm "aginst the class interface" and users only need to supply a class instance for their own data type in order to use your algorithm. What the wiki warns about is misuse or over-use of typeclasses. Typeclasses express properties that different types have in common, and in that respect they are somewhat similar to OO-classes. However, there is no hierarchy of inheritance. It is true that typeclasses, particularly the more advanced ones with e.g. multiple parameters or functional dependencies, sometimes get into your way. One example is ambiguity arising from multi-parameter type classes: Suppose you have a two-parameter class {-# LANGUAGE MultiParamTypeClasses,FunctionalDependencies #-} class Foo a b where foo :: a -> b bar :: b -> (a,[Int]) Now you write a function using only bar: f :: (Foo a b) => b -> Int f = length.snd.bar The compiler will complain that it does not know which Foo instance to use, because while bar itself mentions both class parameters a and b, snd.bar has type b -> [Int] and hence lost the information about the first class parameter. Adding a functional dependency b -> a helps in this case. But the promise that for every b there is only one a such that Foo a b holds may not be what you want. So what went wrong? Observe that bar :: b -> (a,[Int]) is equivalent to two functions bar1 :: b -> a bar2 :: b -> [Int] and bar2 probably did not belong into the class Foo. We've been cramming to much into one typeclass and should therefore split Foo into two classes. Olaf

1 0