I'm not sure Data.Set would work, because afaik, Sets don't preserve
ordering: so a row like "abc" and "cab" would be represented by the same
Set.
Data.Vector is more efficient, but I like it more than List when I have to
do slicing.
hth,
L.
On Fri, Mar 23, 2012 at 10:01 AM, Nathan Hüsken
Firstly, Thanks! I take from the both replies, to first create data-structures for rows, columns and diagonals. That approach makes sense to me.
On 03/23/2012 01:21 AM, Ozgur Akgun wrote:
Hi,
import Data.List import qualified Data.Set as S
rows :: Ord a => [[a]] -> S.Set [a] rows = S.fromList
cols :: Ord a => [[a]] -> S.Set [a] cols = S.fromList . transpose
diagonals :: Ord a => [[a]] -> S.Set [a] diagonals [] = S.empty diagonals xss = S.union ( S.fromList $ transpose (zipWith drop [0..] xss) ) ( diagonals (map init (tail xss)) )
allWords :: Ord a => [[a]] -> S.Set [a] allWords xss = S.unions [ rows xss , cols xss , diagonals xss , diagonals (map reverse xss) ]
... search :: Ord a => [a] -> [[a]] -> Bool search word xss = not $ null [ () | xs <- S.toList (allWords xss), word `isPrefixOf` xs ]
If I understand correctly, in this solution it is assumed that that a word must be a complete line (row column or diagonal), correct? I was not clear in original mail, the word can also be in the middle of line, but it seems easy enough to adjust the sample for this.
I do not understand why a set is used. Couldn't just a list be used here, or is there some performance advantage I do not see?
I find it very difficult to estimate the performance of an haskell program. The other solution of Lorenzo Bolla utilizes Data.Vector. Does that give a performance advantage in this case?
Thanks! Nathan
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners