CODEWITHSUNDEEP
listhaskellrecursion
Loki Clock
Loki Clock

Reputation: 123

Failure to terminate when expanding a list by applying a function to its members til no output is new

Using the Data.List.Ordered library, I was trying to express a function that expands a list by taking each element, applying a function to it and collecting the results in with the original elements without duplicates, and repeating that until no new elements are created. Now, looking at Data.Set, the union operation is O(n+m), and Data.List.Ordered's nubSort is O(n), so this probably doesn't even speed things up, but it didn't work, and I don't know why.

import Data.List.Ordered --install data-ordlist

Consider the following:

nextimg:: Ord a => (a->a)->[a]->[a]
nextimg f x = nubSort $ union (map f x) x

Note that

nextimg ((`mod` 3).(+1)) [1,2]
== nextimg ((`mod` 3).(+1)) [0,1,2]
== [0,1,2]

But if one attempts to perform this recursively:

orbit:: Ord a => (a->a)->[a]->[a]
orbit f x = orbit f ( nubSort $ union (map f x) x )

Then this will run forever:

orbit ((`mod` 3).(+1)) [1]

Upvotes: 1

Views: 102

Answers (2)

Will Ness
Will Ness

Reputation: 71065

better have more granular 

import Data.List.Ordered                -- install data-ordlist

next f xs = nubSort $ map f xs

then 

orbit f xs = snd $ until 
    (\(ys,xs) -> null $ minus ys xs)    -- nothing new to add
    (\(ys,xs) -> (next f $ union ys xs, ys))
    (next xs, xs)

you're supposed to call Data.List.Ordered.union on two ordered lists. (and minus too).

Upvotes: 0

Sassa NF
Sassa NF

Reputation: 5406

Clearly, after you obtained the largest list, nubSort sorted it, and orbit keeps "unioning" only the elements that are already there, and sorting the list that was already sorted. You didn't specify a termination condition - like, possibly:

orbit f x | y == x    = x -- fixed point was found
          | otherwise = orbit f y where
            y = nubSort $ union (map f x) x

Upvotes: 1

Related Questions