On Thu, 19 Oct 2006, Mikael Johansson wrote:

On Thu, 19 Oct 2006, Mikael Johansson wrote:

...

Comparing the code for permutationgropus at http://www.polyomino.f2s.com/david/haskell/codeindex.html with my own thoughts on the matter, I discover the one line to figure out whether a specific list represents the identity:

isIdentity (PL xs) = all (\(i,j) -> i==j) (zip [1..] xs)

Is there any sort of benefit to be won by using this construction instead of

isIdentity (PL xs) = xs == [1..(length xs)]

and if so, what?

At some point in the future, I'll learn to think more before I post. Say

isIdentity xs = all (\(i,j) -> i==j) (zip [1..] xs) isIdentity' xs = xs == [1..(length xs)]

Then isIdentity 1:3:2:[4..100000] finishes in an instant, whereas isIdentity' 1:3:2:[4..100000] takes noticable time before completing.

So it's a question of getting laziness to work for you.

Indeed. The first version works also for infinite lists. That is, if the infinite list does not represent the identity, the function will eventually return False, otherwise it runs forever. Btw. you can simplify this version to: isIdentity (PL xs) = and (zipWith (==) [1..] xs)

On 19/10/06, David House wrote:

On 19/10/06, Mikael Johansson wrote:

...

isIdentity xs = all (\(i,j) -> i==j) (zip [1..] xs) isIdentity' xs = xs == [1..(length xs)]

Then isIdentity 1:3:2:[4..100000] finishes in an instant, whereas isIdentity' 1:3:2:[4..100000] takes noticable time before completing.

Why is this so? I'd have thought that the equality function for lists only forces evaluation of as many elements from its arguments as to determine the answer.

In order to determine if [1..length xs] has an element at all, you have to evaluate length xs, which involves forcing the entire spine of xs, because integers can't be partially evaluated. Computing lengths of lists is a great way to introduce strictness.

On Thu, 19 Oct 2006, Tomasz Zielonka wrote:

On Thu, Oct 19, 2006 at 01:37:16PM -0400, Cale Gibbard wrote:

...

In order to determine if [1..length xs] has an element at all, you have to evaluate length xs, which involves forcing the entire spine of xs, because integers can't be partially evaluated. Computing lengths of lists is a great way to introduce strictness.

Right, so if Ints were represented as a datatype with Succ and Zero constructors (so integers could be partially evaluated), then the version with length would behave nicely on large and infinite lists :-)

Using genericLength for unary, lazy natural numbers can be convenient for other tasks as well, for instance choosing the shorter of two lists in a simple and lazy way. See "Modular Lazy Search for Constraint Satisfaction Problems", Nordin and Tolmach, http://web.cecs.pdx.edu/~apt/, around page 25, for another (related) example. -- /NAD

On Oct 19, 2006, at 12:51 PM, David House wrote:

On 19/10/06, Mikael Johansson wrote:

...

isIdentity xs = all (\(i,j) -> i==j) (zip [1..] xs) isIdentity' xs = xs == [1..(length xs)]

Then isIdentity 1:3:2:[4..100000] finishes in an instant, whereas isIdentity' 1:3:2:[4..100000] takes noticable time before completing.

Why is this so? I'd have thought that the equality function for lists only forces evaluation of as many elements from its arguments as to determine the answer. In other words, the computation should go something like this:

I wondered this too for a minute. I'm pretty sure that the answer is that the 'length' function is the culprit, not (==). Calling 'length' forces the spine of 'xs', which accounts for the extra computation. Just say 'no' to length (when you want laziness). [snip]

-- -David House, dmhouse@gmail.com

Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG

Nicolas Frisby wrote:

I may have missed this in the discussion so far, but it seems we could use a summary.

In short: isIdentity does not check for exact equivalence, only a prefix equivalence. That's why it doesn't exhibit the same time/space behavior as a reformulation based on full equivalence.

Both versions check whether the provided list matches a prefix of [1..], it's just that the formulation with == is written to construct the prefix and then compare, while the version with zipWith (==) relies on zip taking just a prefix of the longer list. The reason the version using == is bad is because it is strict in the (spine of) the first list, because you need to compute length xs before you can begin constructing [1..length xs]. if you arrange to lazily construct the reference list, the functions should be roughly equivalent: isIdentity xs = xs == takeLengthOf xs [1..] where takeLengthOf xs ys = zipWith const ys xs for finite lists, takeLengthOf xs ys == take (length xs) ys Brandon

David House wrote:

On 19/10/06, Brandon Moore wrote:

...

isIdentity xs = xs == takeLengthOf xs [1..] where takeLengthOf xs ys = zipWith const ys xs

You probably mean zipWith (flip const) xs ys. Either way, as long as I didn't write "zipWith const xs ys".

...

for finite lists, takeLengthOf xs ys == take (length xs) ys

This ruins the laziness again:

Hugs.Base> let takeLengthOf xs ys = take (length xs) ys; isIdentity xs = xs == takeLengthOf xs [1..] in isIdentity (1:3:2:[4..10000]) False (210064 reductions, 278075 cells) Hugs.Base> let takeLengthOf = zipWith (flip const); isIdentity xs = xs == takeLengthOf xs [1..] in isIdentity (1:3:2:[4..1000]) False (60 reductions, 114 cells)

It's meant as an explanation, and partial specification: Prelude> let takeLength xs ys = zipWith const ys xs Prelude> Test.QuickCheck.test (\xs ys -> takeLength xs ys == take (length xs) ys) OK, passed 100 tests. This reminds me that QuickCheck only generates finite lists. Brandon

How about this: import List isIdentity (PL xs) = xs `isPrefixOf` [1..] ? Best regards, Henk-Jan van Tuyl On Fri, 20 Oct 2006 01:01:33 +0200, Tomasz Zielonka wrote:

On Thu, Oct 19, 2006 at 04:03:38PM +0200, Mikael Johansson wrote:

...

isIdentity (PL xs) = all (\(i,j) -> i==j) (zip [1..] xs)

isIdentity (PL xs) = xs == [1..(length xs)]

How about a compromise?

isIdentity (PL xs) = xs == zipWith const [1..] xs

Best regards Tomasz _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Met vriendelijke groet, Henk-Jan van Tuyl -- http://Van.Tuyl.eu/ -- Using Opera's revolutionary e-mail client: https://secure.bmtmicro.com/opera/buy-opera.html?AID=789433

Using the base libraries... how sneaky. :) On 10/20/06, David House wrote:

On 20/10/06, Henk-Jan van Tuyl wrote:

...

How about this: import List isIdentity (PL xs) = xs `isPrefixOf` [1..] ?

Nice! Short, lazy and says what it does (onomatopoeic code? :)).

-- -David House, dmhouse@gmail.com _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On 21/10/06, Tomasz Zielonka wrote:

Do you also have this experience with Haskell?: when you feel that some code is not ideal, almost always it can be improved.

One of the recurring features of the #haskell IRC conversations is something called 'Algorithm Golf' (which is a misnomer and should really be 'Algorithm Tennis'): one person will request an algorithm and anyone interested sets about building their own. The results are then shared using lambdabot's Haskell evaluation feature and collaboratively improved. Aside from leading to efficient and natural-looking solutions to people's problems, the rounds are often pedagogical and great fun! Silly spin-offs are also common, leading to such wiki pages as http://haskell.org/haskellwiki/Compose. That particular example was mostly my doing and answers the question 'Can you build a function compose :: [a -> a] -> a -> a, such that a value will be fed into the top of the list and we'll get a result out of the bottom?'. Of course, the sane solution is foldl (flip (.)) id, but after noticing that the State monad permits a particularly elegant solution, execState . mapM modify, the task evolved into 'In how many other monads can we write this function?' The examples get more and more silly until we reach Cont when things disappear off the proverbial horizon into the land of 'How on Earth did Cale ever think of that?'. I'd recommend hanging out in the channel to anyone. :) -- -David House, dmhouse@gmail.com

On Sat, Oct 21, 2006 at 02:33:12PM +0100, David House wrote:

Silly spin-offs are also common, leading to such wiki pages as http://haskell.org/haskellwiki/Compose. That particular example was mostly my doing and answers the question 'Can you build a function compose :: [a -> a] -> a -> a, such that a value will be fed into the top of the list and we'll get a result out of the bottom?'. Of course, the sane solution is foldl (flip (.)) id,

flip (foldl (flip id)) ? I usually use the reverse composition, flip (foldr id).