How to solve the problem of bulls, cows and calves in Haskell?

Question

Haskell

A bull costs 10 rubles, a cow - 5 rubles, a calf - 0.5 rubles. It is necessary to buy 100 heads of cattle for 100 rubles. I was wondering how to solve such a problem in Haskell? In imperative languages, the problem is solved through nested loops, but in Haskell they are not. No matter how much I tried, I could not solve the problem.

Answer 1

One of the options (simple, but not optimal) is this:

Prelude> [(bull, cow, calf) | bull<-[1..10], cow<-[1..20],calf<-[1..200], bull + cow + calf == 100, 10*bull + 5*cow +calf/2 == 100]
[(1.0,9.0,90.0)]

Answer 2

This problem is similar to the DFS depth-first search problem and the backpacking problem.
How to solve it in Haskell - I don't know yet. Need to think. Especially in terms of finding
optimality and generally proving that a solution exists.
The proof is important if you imagine that cow prices are irrational numbers for example.

Answer 3

This is a greedy algorithm. Sorting + folding will solve for any number of any prices.
There is a slightly more fun option when the number of positions available for purchase is limited.