Blockchains such as Ethereum use a stack-register based language on their smart-contract processing virtual machines. That model is very convenient because it provides a simple mechanism to measure the amount of work required to run programs: just fix a cost for each primitive operation and sum.
Suppose that, instead of virtual machines, a blockchain featuring smart-contracts used a functional programming language such as Haskell's core. Is there any simple, accurate way to measure the amount of work required to execute a functional program - keeping in mind that nodes are able to use any evaluation strategy, so such measurement must be universal.
"just fix a cost for each primitive operation and sum" is not easy to do. A blockchain network dynamically determines the true value of its token for whatever value the minimum of its token provides. For eg, a gas is worth whatever the world wants to pay for it to use it as a unit of calculation on the world computer. To accurately measure the effort spent by the network to ensure the unit value of its token , we need a DMMS algorithm(as described in the sidechains paper) & which is nothing but a proof-of-work blockchain.
Each primitive operation needs its own blockchain for its value to be determined accurately. When multiple token are implemented over a single blockchain, for eg colored/custom coins, it cannot accurately measure the value of a unit.
In case of functional language, one could perhaps imagine a lisp blockchain with paul graham's 7 primitives implemented as an opcode (stack based interpretor is irrelevant), which would be turing complete but will suffer from the problem of determining the true value of each opcode; the cheapest one will always be abused as evident on ethereum (suicide function's cheapness was spammed).
Thus, to achieve a functional turing complete blockchain you need a braid network of 7 blockchains, each independently determining the true value of effort required for that primitive calculation.
People who have alternatives to proof-of-work will disagree with the above. Cryptocurrency is a new field and the maths is not mature enough for anyone to make concrete claims.