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 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]  • answer could also be sum$ map sum $map (map length) twoStepFactors but I'm not sure that's better!! – Adam Smith Jul 6 '17 at 16:58 2 Answers 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]


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.

• 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 Jul 7 '17 at 14:46
• 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)] – Adam Smith Jul 7 '17 at 14:48
• 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. – Peter Taylor Jul 7 '17 at 15:29
• 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!) – Adam Smith Jul 7 '17 at 15:36
• Ah, no, I see the problem. I'm also counting some tuples (i, j, i) when L[i] = L[j] – Peter Taylor Jul 7 '17 at 15:46