[Haskell-cafe] List comparisons and permutation group code

[Henning Thielemann]

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)