Lucky Triples in Haskell

Question

In answering this question on Stack Overflow, I decided to stretch my legs in Haskell a bit to see if I could implement a solution to find the count of lucky triples in a list of ints.

A lucky triple is any triple (j, k, l) where j <= k <= l and l `mod` k == 0 && k `mod` j == 0. A correct implementation counts how many unique combinations of elements of an [Int] are valid lucky triples.

import Data.List (sort)
answer :: [Int] -> Int
answer xs = foldr ((+) . foldr ((+) . length) 0) 0 $ twoStepFactors
 where
 twoStepFactors = map mapFactors $ mapFactors $ sort xs
mapFactors :: [Int] -> [[Int]]
mapFactors xs = mapFactors' xs []
mapFactors' [] acc = acc
mapFactors' (x:xs) acc = mapFactors' xs newAcc 
 where
 factors = filter ((==0) . (`mod` x)) xs
 newAcc | null factors = acc
 | otherwise = acc ++ [factors]

• Adam Smith: answer could also be sum $ map sum $ map (map length) twoStepFactors but I'm not sure that's better!!

Answer 1

If mapFactors' is put in a where clause of mapFactors, it isn't globally accessible and you can call it go or something because the scoping already points out it belongs to mapFactors.

Swapping gos argument order lets you say mapFactors = go [].

++ [_] is a smell. Instead of passing down an accumulator and growing it to the right, you can pass it out as the return value and grow it to the left.

mapFactors :: [Int] -> [[Int]]
mapFactors = go where
 go [] = []
 go (x:xs) = newAcc $ go xs where
 factors = filter ((==0) . (`mod` x)) xs
 newAcc | null factors = id
 | otherwise = (:) factors

The filtering can happen after go is done.

mapFactors :: [Int] -> [[Int]]
mapFactors = filter (not . null) . go where
 go [] = []
 go (x:xs) = filter ((==0) . (`mod` x)) xs : go xs

tails helps express go in terms of map:

mapFactors :: [Int] -> [[Int]]
mapFactors = filter (not . null) . map go . tails where
 go [] = []
 go (x:xs) = filter ((==0) . (`mod` x)) xs

Let's use sum from that comment and inline the once-used twoStepFactors (imo if you're only giving a name to explain what something does, use comments)

answer :: [Int] -> Int
answer xs = sum $ map (sum . map length . mapFactors) $ mapFactors $ sort xs

There doesn't seem to be a reason to filter out the []s.

List comprehensions neatly let us skip the empty tail, and get rid of go.

mapFactors :: [Int] -> [[Int]]
mapFactors xss = [filter ((==0) . (`mod` x)) xs | x:xs <- tails xss]

Answer 2

I'm not seeing the point of sort or mapFactors. The relationship between j and l is just the transitive relationship through k, so the total number of lucky triples is the sum over k of (number of j which work with this k) times (number of l which work with this k). Emphasis on number of: there's no need to generate an [Int] or to count them in any particular order.

• Adam Smith: sorting once allows me to find products without searching the entire list, saving me an n^2 run over the list. I'm not sure how to implement the algorithm you outline (and not completely sure I understand what you mean by "sum over k"), but I think you mean to count the factors of each element present in the list, subtract one from that (since k will always be a factor of k), then multiply that by itself less one? I'm not sure that's correct, since it implies that no two factors would be co-prime which is obviously false.
• Adam Smith: e.g. in the list [1..6], evaluating 6 would give factors [6, 3, 2, 1]. Applying that algorithm would seem to give 6 pairs: [(3, 1), (2, 1)] which are accurate, but also [(3, 2)] which are co-prime, and all their inverses [(1, 3), (1, 2), (2, 3)]
• Peter Taylor: It still looks n^2 to me, and in fact I think it has to be: consider the extreme case where all the elements of the list are equal. Python implementation to show what I mean.
• Adam Smith: Your implementation doesn't handle duplicate numbers well. Try answer([1,1,1]) (which should be one, since (1, 1, 1) is itself a lucky triple). Regardless in a sorted list you only need to compare each element of index j with elements of index >j. No element of index <=j can be a valid product (except itself, but that's double-dipping!)
• Peter Taylor: Ah, no, I see the problem. I'm also counting some tuples (i, j, i) when L[i] = L[j]