[Haskell-cafe] For Project Euler #24 you don't need to generate all the lexicographic permutations Spoiler
For Project Euler #24 you don't need to generate all the lexicographic permutations by Knuth's method or any other. You're only looking for the millionth lexicographic permutation of 0123456789 Problem 24 A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210 What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9? Spoiler Spoiler Spoiler Plan of attack: -- The xs are different numbers -- 0x represents 9! = 362880 permutations/numbers -- 1x represents 9! = 362880 permutations/numbers -- 2x represents 9! = 362880 permutations/numbers -- 20 represents 8! = 40320 -- 21 represents 8! = 40320 -- 23 represents 8! = 40320 -- 24 represents 8! = 40320 -- 25 represents 8! = 40320 -- 26 represents 8! = 40320 -- 27 represents 8! = 40320 etc. Spoiler Spoiler -- lexOrder 0123456789 100 lexOrder digits left s | len == 0 = s ++ digits | quot 0 rem == 0 = lexOrder (digits\\(show (digits!!(quot-1 rem (s ++ [(digits!!(quot-1))]) | quot == 0 rem == 0 = lexOrder (digits\\(show (digits!!len))) rem (s ++ [(digits!!len)]) | rem == 0 = lexOrder (digits\\(show (digits!!(quot+1 rem (s ++ [(digits!!(quot+1))]) | otherwise = lexOrder (digits\\(show (digits!!(quotrem (s ++ [(digits!!(quot))]) where len = (length digits) - 1 facLen = factorial len (quot,rem) = quotRem left facLen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Division: Is there a way to simultaneously find the quotient and remainder?
:) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] For Project Euler #1 isn't it more efficient to generate just the numbers you need? Spoiler
-- Instead of this -- sumMultiples3or5 s = sum [x | x - [3..s-1], x `mod` 3 == 0 || x `mod` 5 == 0] -- Isn't this faster sumMultiples3or5 s = sum ([x | x - [3,6..s-1]] `merge` [x | x - [5,10..s-1]]) merge xs [] = xs merge [] ys = ys merge txs@(x:xs) tys@(y:ys) | x y = x : xs `merge` tys | x y = y : txs `merge` ys | otherwise = x : xs `merge` ys ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Computational Semantics w/ Functional Programming, Jan van Eijck and Christina Unger, 2010. It's in #Haskell. :)
This may have already been mentioned but it is worth mentioning n times: Computational Semantics w/ Functional Programming, Jan van Eijck and Christina Unger, 2010. It's in #Haskell. :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] want to start a page of Haskell examples to go with Skiena's book The Algorithm Design Manual and also tie in Bird's equational reasoning for functional programming; ...
I want to start a page of Haskell examples to go with Skiena's book The Algorithm Design Manual and also tie in Bird's equational reasoning for functional programming; where is a good place for such examples. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] -- Extension for Pearls of Functional Algorithm Design by Richard Bird, 2010, page 25 #Haskell -- Extension for Pearls of Functional Algorithm Design by Richard Bird, -- 2010, page
-- Extension for Pearls of Functional Algorithm Design by Richard Bird, 2010, page 25 #Haskell -- O(log|X|+log|Y|+log|Z|) performance -- Question: is there a way to get the type signature as the following: -- smallest :: (Ord a) = Int - [Array Int a] - a module SelectionProblem where import Data.Array import Data.List -- Works on 2 finite ordered disjoint sets represented as sorted arrays. smallest :: (Ord a) = Int - (Array Int a, Array Int a) - a smallest k (xa,ya) = search k (xa,ya) (0,m+1) (0,n+1) where (0,m) = bounds xa (0,n) = bounds ya -- Removed some of the indexitis at the cost of calling another function. search :: (Ord a) = Int - (Array Int a, Array Int a) - (Int,Int) - (Int,Int) - a search k (xa,ya) (lx,rx) (ly,ry) | lx == rx = ya ! (k+ly) | ly == ry = xa ! (k+lx) | otherwise = case (xa ! mx ya ! my) of ~~(True)- smallest2h k (xa,ya) ((lx,mx,rx),(ly,my,ry)) ~~(False) - smallest2h k (ya,xa) ((ly,my,ry),(lx,mx,rx)) ~~where ~~mx = (lx+rx) `div` 2 ~~my = (ly+ry) `div` 2 -- Here the sorted arrays are in order by their middle elements. -- Only cutting the leading or trailing array by half. -- Here xa is the first array and ya the second array by their middle elements. smallest2h :: (Ord a) = Int - (Array Int a, Array Int a) - ((Int,Int,Int),(Int,Int,Int)) - a smallest2h k (xa,ya) ((lx,mx,rx),(ly,my,ry)) = case (k=mx-lx+my-ly) of ~~(True)- search k (xa,ya) (lx,rx) (ly,my) ~~(False) - search (k-(mx-lx)-1) (xa,ya) (mx+1,rx) (ly,ry) --- --- -- Works on 3 finite ordered disjoint sets represented as sorted arrays. smallest3 :: (Ord a) = Int - (Array Int a, Array Int a, Array Int a) - a smallest3 k (xa,ya,za) = -- On each recursive call the order of the arrays can switch. search3 k (xa,ya,za) (0,bx+1) (0,by+1) (0,bz+1) where (0,bx) = bounds xa (0,by) = bounds ya (0,bz) = bounds za -- Removed some of the indexitis at the cost of calling another function. search3 :: (Ord a) = Int - (Array Int a, Array Int a, Array Int a) - (Int,Int) - (Int,Int) - (Int,Int) - a search3 k (xa,ya,za) (lx,rx) (ly,ry) (lz,rz) | lx == rx ly == ry = za ! (k+lz) | ly == ry lz == rz = xa ! (k+lx) | lx == rx lz == rz = ya ! (k+ly) | lx == rx = search k (ya,za) (ly,ry) (lz,rz) | ly == ry = search k (xa,za) (lx,rx) (lz,rz) | lz == rz = search k (xa,ya) (lx,rx) (ly,ry) | otherwise = case (xa ! mx ya ! my, xa ! mx za ! mz, ya ! my za ! mz) of ~~(True, True, True)- smallest3h k (xa,ya,za) ((lx,mx,rx),(ly,my,ry),(lz,mz,rz)) -- abc ~~(True, True, False) - smallest3h k (xa,za,ya) ((lx,mx,rx),(lz,mz,rz),(ly,my,ry)) -- acb ~~(False, True, True) - smallest3h k (ya,xa,za) ((ly,my,ry),(lx,mx,rx),(lz,mz,rz)) -- bac ~~(False, False, True) - smallest3h k (ya,za,xa) ((ly,my,ry),(lz,mz,rz),(lx,mx,rx)) -- bca ~~(True, False, False) - smallest3h k (za,xa,ya) ((lz,mz,rz),(lx,mx,rx),(ly,my,ry)) -- cab ~~(False, False, False) - smallest3h k (za,ya,xa) ((lz,mz,rz),(ly,my,ry),(lx,mx,rx)) -- cba ~~where ~~mx = (lx+rx) `div` 2 ~~my = (ly+ry) `div` 2 ~~mz = (lz+rz) `div` 2 -- Here the sorted arrays are in order by their middle elements. -- Only cutting the leading or trailing array by half. -- Here xa is the first array, ya the second array, and za the third array by their middle elements. smallest3h :: (Ord a) = Int - (Array Int a, Array Int a, Array Int a) - ((Int,Int,Int),(Int,Int,Int),(Int,Int,Int)) - a smallest3h k (xa,ya,za) ((lx,mx,rx),(ly,my,ry),(lz,mz,rz)) = case (k=mx-lx+my-ly+mz-lz) of ~~(True)- search3 k (xa,ya,za) (lx,rx) (ly,ry) (lz,mz) ~~(False) - search3 (k-(mx-lx)-1) (xa,ya,za) (mx+1,rx) (ly,ry) (lz,rz) --- --- -- To convert a list into an array indexed from 0. xa = listArray (0, length xs - 1) xs ya = listArray (0, length ys - 1) ys za = listArray (0, length zs - 1) zs xs = [0,17..90] ys = [1,13..69] zs = [7,24..91] ua = listArray (0, length us - 1) us va = listArray (0, length vs - 1) vs wa = listArray (0, length ws - 1) ws us = [0,17..100] vs = [101,121..200] ws = [201,221..300] -- *SelectionProblem sort (xs++ys++zs) -- [0,1,7,13,17,24,25,34,37,41,49,51,58,61,68,75,85] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org
[Haskell-cafe] -- Extension for Pearls of Functional Algorithm Design by Richard Bird, 2010, page 25 #Haskell
-- Extension for Pearls of Functional Algorithm Design by Richard Bird, -- 2010, page 25 #Haskell -- This version assumes 3 disjoint ordered sets represented as lists. -- So either: xy XOR xy -- Since it uses lists it is no faster than the divide and conquer approach. -- I might try to convert this version to sorted arrays for -- O(log|X|+log|Y|+log|Z|) performance -- If I can figure out how to do it without suffering from indexitis. smallest3'' :: Ord a = Int - ([a], [a], [a]) - a smallest3'' k ([],[],ts) = ts !! k smallest3'' k (zs,[],[]) = zs !! k smallest3'' k ([],ws,[]) = ws !! k smallest3'' k ([],ws,ts) = smallest'' k (ws,ts) smallest3'' k (zs,[],ts) = smallest'' k (zs,ts) smallest3'' k (zs,ws,[]) = smallest'' k (zs,ws) smallest3'' k (zs,ws,ts) = case (ab, bc, ac) of ~~(True, True, True)- smallest3h'' k ((zs,p,ys),(ws,q),(ts,o,rs)) -- abc ~~(True, False, True) - smallest3h'' k ((zs,p,ys),(ts,o),(ws,q,us)) -- acb ~~(False, True, True) - smallest3h'' k ((ws,q,vs),(zs,p),(ts,o,rs)) -- bac ~~(False, True, False) - smallest3h'' k ((ws,q,vs),(ts,o),(zs,p,xs)) -- bca ~~(True, False, False) - smallest3h'' k ((ts,o,ss),(zs,p),(ws,q,us)) -- cab ~~(False, False, False) - smallest3h'' k ((ts,o,ss),(ws,q),(zs,p,xs)) -- cba where ~~p = (length zs) `div` 2 ~~q = (length ws) `div` 2 ~~o = (length ts) `div` 2 ~~(xs, a : ys) = splitAt p zs ~~(us, b : vs) = splitAt q ws ~~(rs, c : ss) = splitAt o ts ~~smallest3h'' k ((zs,p,ys),(ws,q),(ts,o,rs)) = case (k=p+q+o) of ~~(True)- smallest3'' k (zs,ws,rs) ~~(False) - smallest3'' (k-p-1) (ys,ws,ts) smallest'' :: Ord a = Int - ([a], [a]) - a smallest'' k ([],ws) = ws !! k smallest'' k (zs,[]) = zs !! k smallest'' k (zs,ws) = case (ab, k=p+q) of ~~(True, True) - smallest'' k (zs,us) ~~(True, False) - smallest''(k-p-1) (ys,ws) ~~(False, True) - smallest'' k (xs,ws) ~~(False, False)- smallest''(k-q-1) (zs,vs) where ~~p = (length zs) `div` 2 ~~q = (length ws) `div` 2 ~~(xs, a : ys) = splitAt p zs ~~(us, b : vs) = splitAt q ws ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Errata for Pearls of Functional Algorithm Design by Richard Bird, 2010, page 25 #Haskell
-- Errata for Pearls of Functional Algorithm Design by Richard Bird, -- 2010, page 25 #Haskell -- I don't like this solution it suffers from indexitis which -- Bird talks about in the chapter on Sudoku. -- I can see why lists are liked, they avoid indexitis at -- the cost of chopping and concatenating them. -- One of the advantages of functional programming is supposed to be less bookkeeping. smallest :: (Ord a) = Int - (Array Int a, Array Int a) - a smallest k (xa,ya) = search k (0,m+1) (0,n+1) where (0,m) = bounds xa (0,n) = bounds ya search k (lx,rx) (ly,ry) | lx == rx = ya ! (k+ly) | ly == ry = xa ! (k+lx) | otherwise = case (xa ! mx ya ! my, k = mx-lx+my-ly) of ~~(True, True) - search k (lx,rx) (ly,my) ~~(True, False) - search (k-(mx-lx)-1) (mx+1,rx) (ly,ry) ~~(False, True) - search k (lx,mx) (ly,ry) ~~(False, False)- search (k-(my-ly)-1) (lx,rx) (my+1,ry) ~~where ~~mx = (lx+rx) `div` 2 ~~my = (ly+ry) `div` 2 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Adjoint Folds and Unfolds Or: Scything through the Thicket of Morphisms
Just tripped over this: Adjoint Folds and Unfolds Or: Scything through the Thicket of Morphisms Folds and unfolds are at the heart of the algebra of programming. They allow the cognoscenti to derive and manipulate programs rigorously... Ralf Hinze Lecture Notes in Computer Science, 2010, Volume 6120, Mathematics of Program Construction, Pages 195-228 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Denotational semantics for the lay man.
You probably want to bring up other forms of semantics. Axiomatic semantics: Makes no distinction between a phrase's meaning and the logical formulas that describe it; its meaning is exactly what can be proven about it in some logic. Operational semantics: The execution of the language is described directly (rather than by translation). Operational semantics loosely corresponds to interpretation. Can be defined via syntactic transformations on phrases of the language itself. Denotational semantics: each phrase in the language is translated into a denotation, i.e. a phrase in some other language. Denotational semantics loosely corresponds to compilation, although the target language is usually a mathematical formalism rather than another computer language. Above from Wikipedia. Quoting David Sankel cam...@gmail.com: Hello All, I've recently had the opportunity to explain in prose what denotational semantics are to a person unfamiliar with it. I was trying to get across the concept of distilling the essence out of some problem domain. I wasn't able to get the idea across so I'm looking for some simple ways to explain it. Does anyone know of a way to explain what's the meaning and objective of distilling the essence without introducing more jargon. One thing that comes to mind is how Newton's equations for gravity were a distillation of the essence of the way things fall. Thanks in advance, David -- David Sankel Sankel Software www.sankelsoftware.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Guy Steele's Praise For Haskell @ Strange Loop Keynote
Quoting Brandon S Allbery KF8NH allb...@ece.cmu.edu: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 1/15/11 18:15 , Warren Henning wrote: MATLAB, LabVIEW, Fortran, Java, C, and non-OO C++/random subsets of C++ rule scientific programming. Unit testing is rare and sporadic. In dragging scientists halfway to something new, the exotic, powerful things in Haskell will have to be left behind, just as Java only has a tiny fraction of what Smalltalk has had since the '80s. That seems clear to me, anyway. Scipy seems to be doing a decent job of throwing that into question. Throwing which part into question? - -- brandon s. allbery [linux,solaris,freebsd,perl] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.11 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] H98, OOHaskell - getting started with objects in Haskell
If you want to use an OO approach: try thinking of a sparse array of objects (previous and current generations) where each object knows its coordinates by being linked into a sparse array data structure. Quoting gutti philipp.guttenb...@gmx.net: On Fri, 14 Jan 2011 12:36:22 -0800 (PST) Wolfgang Jeltsch-2 [via Haskell] ml-node+3341886-976283800-146...@n5.nabble.com wrote: Is this really ideal for OO? I thought that in a cellular automaton, all cells have to change synchronously. In addition, cells have to access the old states of their neighbours to compute their new states. So you would have to heavily synchronize the objects. In this light, I?d say that the distributed OO approach isn?t very practical. A global control of the whole system might be better. Note that I?m by no way an expert in cellular automata. I?m just thinking of the game of life. :-) Best wishes, Wolfgang Hi Wolfgang, I don't yet have experience with cellular automata either. What u say seems plausible, but then the life game might have been coded that way, because most OO language don't offer concurrent objects and the distributed OO approach (seems to be a very recent concept). Looking at life u probably could save time, if u only would evaluate code on cells, where the neighbors have changed status. So rather than triggering them all centrally and each checks its neighbours, we could use the concept: - let the active ones trigger the neighbours so pass on activity ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Monad Syntax
From: A Neighborhood of Infinity Monday, August 07, 2006 You Could Have Invented Monads! (And Maybe You Already Have.) http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html The following part: do let x = 7 y - Writer (x+1,inc\n) z - Writer (2*y,double\n) Writer (z-1,dec\n) The notation is very suggestive. When we write y - ... it's as if we can pretend that the expression on the right hand side is just x+1 and that the side-effect just looks after itself. Why pretend? Couldn't the syntax be: do let x = 7 y - x+1, Writer (inc\n) z - 2*y, Writer (double\n) z-1, Writer (dec\n) Or some other delimiter than the comma? I'm thinking this syntax might be easier to understand. :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Hood on Hackage is an interesting way to see intermediate data structures.
Hood on Hackage is an interesting way to see intermediate data structures.
{-# LANGUAGE NoMonomorphismRestriction #-}
-- Fold Behaviour Observed
module Folding where
-- See Hood on Hackage
import Observe
import Data.List
n = 10::Int
fr = foldr (observe Add (+)) 0 [1..n]
fl = foldl (observe Add (+)) 0 [1..n]
frr = foldr (observe Add (+)) 0 (reverse [1..n])
flr = foldl (observe Add (+)) 0 (reverse [1..n])
fro = printO fr
flo = printO fl
frro = printO frr
flro = printO flr
fl' = foldl' (observe Add (+)) 0 [1..n]
flr' = foldl' (observe Add (+)) 0 (reverse [1..n])
flo' = printO fl'
flro' = printO flr'
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] If Python now has a good email library; how challenging is it to call Python from Haskell?
:) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Is it possible to easily connect Haskell to JavaScript/JavaFX in the browser and use a browser as a Windows GUI? :)
Is it possible to easily connect Haskell to JavaScript/JavaFX in the browser and use a browser as a Windows GUI? :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell Front Page Ideas
How about a bullet list of Haskell's features (maybe pros cons) might be better; followed by a list of a few other languages and their trade-offs. As Jon Bentley has said, design is usually trade-offs but when you can come up with something that is a mutual benefit; so much the better. :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] I'm still having challenges to get a Haskell GUI to work under Windows 7
I'm still having challenges to get a Haskell GUI to work under Windows 7; even after various instructions on the web. e.g. Haskell Platform 2010.2.0.0, wxWidgets-2.9.1, wxHaskell 0.12.1.6 Similar challenges with GTK+ and gtk2hs. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Is there a more recent paper or article than Can GUI Programming Be Liberated From The IO Monad
Is there a more recent paper or article than Can GUI Programming Be Liberated From The IO Monad? :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] I still cannot seem to get a GUI working under Windows.
I still cannot seem to get a GUI working under Windows. For Haskell GUI's is Ubuntu easier to setup. If so, we're losing people if Haskell GUI's are so hard to get working under Windows. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] When I change the cabal file to say preference: base = 4
When I change the cabal file to say preference: base = 4 I still get, you are using base 3.0 which is deprecated. When I change the overall cabal profile, the error message still comes up. It seems like some other part of the install process is controlling the base version, besides the *.cabal and cabal profile file. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Why can't libraries/frameworks like wxHaskell/gtk2hs/... be used with newer versions of ghc/wxWidgets/GTK+/... ?
Why can't libraries/frameworks like wxHaskell/gtk2hs/... be used with newer versions of ghc/wxWidgets/GTK+/... ? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Does Hackage have a connection to some SFT package (Significant FFT coefficients) ...
Does Hackage have a connection to some SFT package (Significant FFT coefficients) and/or can one get the SFT from FFTW without generating all the coefficients? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How does one get off haskell?
Quoting Andrew Coppin andrewcop...@btinternet.com: Serguey Zefirov wrote: I should suggest code generation from Haskell to C#/Java and PHP. Like Barrelfish, Atom, HJScript and many others EDSLs out there. You will save yourself time, you will enjoy Haskell. Probably, you will have problems with management because your programs will appear there in their completeness very suddently. ; I would imagine a bigger problem is that machine-generated C# is probably incomprehensible to humans. ;-) Most machine-generated code is probably incomprehensible to humans. :) What one wants is a translator back and forth, if one could understand the machine-generated code. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] In other words is there a good place to post stuff like the following?
-- Algorithms From: Selected Papers on Design of Algorithms, Donald Knuth, 2010 -- Chapter 10 Addition Machines -- Haskell version by Casey Hawthorne -- Note this is only a skeleton of the chapter, -- so as to wet your interest to buy the book. -- Addition Machine -- The only operations allowed are the following: -- read x -- x - y -- x - x + y -- x - x - y -- if x = y -- write x -- Can all functional versions be tail recursive? --- --- -- Modulus -- Assuming without loss of generality x=0 and y0, -- since one can use various identities for other cases. -- Performs floor(x/y) subtractions. modulusNaive x y | x = y= modulusNaive (x-y) y | otherwise = x -- Can we do better? -- Uses a doubling procedure to subtract larger multiplies of y. -- Bounded by O(log(x/y))^2 modulusByDoubling x y | x = y= helper y y | otherwise = x where helper w z | x z = helper z z+z | otherwise = modulusByDoubling (x-w) y -- Can we do better? -- Want bounded by O(log(x/y)). -- Addition Machine, so cannot divide by 2. -- Implicitly use the Fibonacci representation of floor(x/y) -- instead of its the binary representation. -- F0 = 0; F1 = 1; Fn = F(n-1) + F(n-2), n =2 -- Every nonnegative integer n can be uniquely represented in the form -- n = F(m1) + F(m2) + ... + F(mt), m1 m2 ... mt 0 -- where t = 0 and m m' means that m - m' = 2 -- If n 0 this representation can be found by choosing m1 such that -- F(m1) = n F(m1+1) --- -- Furthermore Fibonacci numbers grow exponentially, -- about 69% as fast as powers of 2. -- They have been used as power-of-2 analogs in a variety of algorithms. --- modulusFib x y | x = y= helper x y y | otherwise = x where helper x y z | x z = helper x z y+z | otherwise = helper2 x y z helper2 x y z | x = y= helper2 (x-y) y z | y z = helper2 x (z-y) y | otherwise = x ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] In other words is there a good place to post stuff like the following?
-- Algorithms From: Selected Papers on Design of Algorithms, Donald Knuth, 2010 -- Chapter 10 Addition Machines -- Haskell version by Casey Hawthorne -- Note this is only a skeleton of the chapter, -- so as to wet your interest to buy the book. -- Addition Machine -- The only operations allowed are the following: -- read x -- x - y -- x - x + y -- x - x - y -- if x = y -- write x -- Can all functional versions be tail recursive? --- --- -- Modulus -- Assuming without loss of generality x=0 and y0, -- since one can use various identities for other cases. -- Performs floor(x/y) subtractions. modulusNaive x y | x = y= modulusNaive (x-y) y | otherwise = x -- Can we do better? -- Uses a doubling procedure to subtract larger multiplies of y. -- Bounded by O(log(x/y))^2 modulusByDoubling x y | x = y= helper y y | otherwise = x where helper w z | x z = helper z z+z | otherwise = modulusByDoubling (x-w) y -- Can we do better? -- Want bounded by O(log(x/y)). -- Addition Machine, so cannot divide by 2. -- Implicitly use the Fibonacci representation of floor(x/y) -- instead of its the binary representation. -- F0 = 0; F1 = 1; Fn = F(n-1) + F(n-2), n =2 -- Every nonnegative integer n can be uniquely represented in the form -- n = F(m1) + F(m2) + ... + F(mt), m1 m2 ... mt 0 -- where t = 0 and m m' means that m - m' = 2 -- If n 0 this representation can be found by choosing m1 such that -- F(m1) = n F(m1+1) --- -- Furthermore Fibonacci numbers grow exponentially, -- about 69% as fast as powers of 2. -- They have been used as power-of-2 analogs in a variety of algorithms. --- modulusFib x y | x = y= helper x y y | otherwise = x where helper x y z | x z = helper x z y+z | otherwise = helper2 x y z helper2 x y z | x = y= helper2 (x-y) y z | y z = helper2 x (z-y) y | otherwise = x ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] What is Haskell unsuitable for? Dis-functional programming!
:) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] The functional-object style seems to be gaining momentum.
The functional-object style seems to be gaining momentum. Is there any way to convert monads into objects, so that beginners have an easier time with the syntax and thus we can attract more people to the language? :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What is Haskell unsuitable for?
If you want to use cool languages, you may have to get a cool job. I know: it's easy to say and harder to accomplish. Most functional languages (e.g. Lisp, Haskell, ...) have a challenging time in industry since they require some savvy with multiple levels of higher abstractions and some savvy with mathematical ideas and some savvy with functional algorithms and data structures. Also, your manager has probably come up through the technical ranks on his/her OOA/OOD/OOP skills and sees you as a young (or not) upstart trying to show off. :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Math questions
Quoting Mujtaba Boori mujtaba.bo...@gmail.com: Hello I am try to solve this equation Define a higher order function that tests whether two functions , both defined on integers , coincide for all integers between 1 and 100 how can I solve this ? is there any thing in Haskell library to solve this kind ? -- Mujtaba Ali Alboori This sounds like homework. In any case, won't your HOF take as input the two functions and the input range to check. Then think about how you might compare the output of the two functions. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Books for advanced Haskell
CBV = Call By Value, essentially strict evaluation CBN = Call By Name Call by Need = Call-by-need is a memoized version of call-by-name; essentially lazy evaluation CBL = Maybe a new acronym for Call by Need. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] QOTM: It's a series of 3 TLAs designed to make people who know what they are feel more in-the-know than those who don't.
CBV, CBN, CBL ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] If monads are single/linearly threaded, doesn't that reduce parallelism?
___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
