Re: [Haskell-cafe] Being impure within a 'pure' function
Well, thanks to all of you. Daniel 2009/4/23 Daniel Fischer daniel.is.fisc...@web.de Am Donnerstag 23 April 2009 14:15:16 schrieb Max Rabkin: On Wed, Apr 22, 2009 at 10:38 AM, Daniel K. anmeldema...@gmail.com wrote: Dijkstra's algorithm ... relies heavily on mutating arrays Well, the imperative implementation does. Not mutating the underlying arrays would probably result in poor performance. Indeed. Non-mutable arrays are not very performant for mutations. Tree-like data structures Are Your Friend. I've never compared the performance of an ST-based implementation with a set/map based algorithm, but I've often found the latter usably performant. I have occasionally, and I can confirm that often set/map based algorithms give quite usable performance. But usually ST-based implementations are significantly faster. If the algorithm demands a lot of updates and performance is important, I recommend sacrificing the ease and elegance of coding with sets/maps for ST's uglier but faster code (but verify that set/map performance is unsatisfactory first). --Max ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Being impure within a 'pure' function
On Wed, Apr 22, 2009 at 10:38 AM, Daniel K. anmeldema...@gmail.com wrote: Dijkstra's algorithm ... relies heavily on mutating arrays Well, the imperative implementation does. Not mutating the underlying arrays would probably result in poor performance. Indeed. Non-mutable arrays are not very performant for mutations. Tree-like data structures Are Your Friend. I've never compared the performance of an ST-based implementation with a set/map based algorithm, but I've often found the latter usably performant. --Max ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Being impure within a 'pure' function
Am Donnerstag 23 April 2009 14:15:16 schrieb Max Rabkin: On Wed, Apr 22, 2009 at 10:38 AM, Daniel K. anmeldema...@gmail.com wrote: Dijkstra's algorithm ... relies heavily on mutating arrays Well, the imperative implementation does. Not mutating the underlying arrays would probably result in poor performance. Indeed. Non-mutable arrays are not very performant for mutations. Tree-like data structures Are Your Friend. I've never compared the performance of an ST-based implementation with a set/map based algorithm, but I've often found the latter usably performant. I have occasionally, and I can confirm that often set/map based algorithms give quite usable performance. But usually ST-based implementations are significantly faster. If the algorithm demands a lot of updates and performance is important, I recommend sacrificing the ease and elegance of coding with sets/maps for ST's uglier but faster code (but verify that set/map performance is unsatisfactory first). --Max ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Being impure within a 'pure' function
Hello, imagine the following situation: You want to implement e.g. Dijkstra's algorithm to find a shortest path between nodes u and v in a graph. This algorithm relies heavily on mutating arrays, so the type signature would look something like getDistance :: Graph - Node - Node - IO Int Not mutating the underlying arrays would probably result in poor performance. BUT: For a constant graph, the distance between two nodes stays the same all the time, so in fact getDistance should be a pure function! So here is my question: Is there a way to write functions in Haskell that do some IO internally, but that are guaranteed to be side-effect free? Of course one would have to make sure that the array that is mutated inside getDistance must not be accessible from outside the function. Is that possible? If not, wouldn't that be desirable? If not, why not? Thanks Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Being impure within a 'pure' function
Yes. Use the ST (State Thread) monad. Data.Array.ST, STRef etc. 2009/4/22 Daniel K. anmeldema...@gmail.com: Hello, imagine the following situation: You want to implement e.g. Dijkstra's algorithm to find a shortest path between nodes u and v in a graph. This algorithm relies heavily on mutating arrays, so the type signature would look something like getDistance :: Graph - Node - Node - IO Int Not mutating the underlying arrays would probably result in poor performance. BUT: For a constant graph, the distance between two nodes stays the same all the time, so in fact getDistance should be a pure function! So here is my question: Is there a way to write functions in Haskell that do some IO internally, but that are guaranteed to be side-effect free? Of course one would have to make sure that the array that is mutated inside getDistance must not be accessible from outside the function. Is that possible? If not, wouldn't that be desirable? If not, why not? Thanks Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Eugene Kirpichov Web IR developer, market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Being impure within a 'pure' function
If you want to do raw IO and repackage it as pure, you can use `unsafePerformIO` and friends. It is important to use the `NOINLINE` pragma in that case. -- Jason Dusek |...unsafePerformIO...| http://haskell.org/ghc/docs/latest/html/libraries/base/System-IO-Unsafe.html#v%3AunsafePerformIO ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Being impure within a 'pure' function
On 22 Apr 2009, at 10:38, Daniel K. wrote: Hello, imagine the following situation: You want to implement e.g. Dijkstra's algorithm to find a shortest path between nodes u and v in a graph. This algorithm relies heavily on mutating arrays, so the type signature would look something like getDistance :: Graph - Node - Node - IO Int Not mutating the underlying arrays would probably result in poor performance. BUT: For a constant graph, the distance between two nodes stays the same all the time, so in fact getDistance should be a pure function! So here is my question: Is there a way to write functions in Haskell that do some IO internally, but that are guaranteed to be side- effect free? Of course one would have to make sure that the array that is mutated inside getDistance must not be accessible from outside the function. Is that possible? If not, wouldn't that be desirable? If not, why not? Either, as Eugene suggested, use the ST monad, as is possible in this case (and much better than the solution I'm proposing), or if you *really* can't get out of using IO, use unsafePerformIO. You will though have to provide several guarantees yourself that the type system would normally provide for you (hence the unsafe part - it should really be verifyItsSafeYourselfPerformIO). Bob ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Being impure within a 'pure' function
Hello Jason, Wednesday, April 22, 2009, 1:14:49 PM, you wrote: there is no any need in unsafePerformIO for array computations - ST monad is exactly what one need here If you want to do raw IO and repackage it as pure, you can use `unsafePerformIO` and friends. It is important to use the `NOINLINE` pragma in that case. -- Jason Dusek |...unsafePerformIO...| http://haskell.org/ghc/docs/latest/html/libraries/base/System-IO-Unsafe.html#v%3AunsafePerformIO ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
